Problem complexity & NP-completeness

Reading time10 min

En bref

Résumé de l’article

Jusqu’à présent, nous avons étudié la complexité des algorithmes, comme moyen d’estimer le temps nécessaire à leur exécution, en fonction de leurs entrées. Plus généralement, les problèmes ont une notion de complexité. Cela signifie que pour un problème donné, on ne peut pas trouver un algorithme avec une meilleure complexité pour le résoudre.

Points clés

  • Il existe des classes de complexité pour les problèmes.

  • La complexité d’un problème décrit la complexité minimale d’un algorithme le résolvant.

  • Il existe des intersections, des relations d’inclusion ou des équivalences entre certaines classes de complexité.

  • La complexité peut aussi décrire la mémoire requise pour résoudre un problème.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez aussi lire les transcriptions si vous préférez.

Information

Salut ! Vous êtes revenu ? Super ! Cela signifie que vous n’avez pas encore eu assez de complexité !

Aujourd’hui, explorons ce que sont les problèmes P et NP, et comment cela impacte la résolution des problèmes.

Complexité d’un problème

La complexité d'un problème est liée à la complexité des algorithmes. La complexité d'un problème est définie comme la complexité minimale des algorithmes qui résolvent ce problème.

Comme nous l’avons vu la semaine dernière, la complexité d’un algorithme inclut une connotation de “pire cas”, car elle mesure le nombre “maximum” d’opérations élémentaires nécessaires à son exécution.

Par conséquent, la complexité d'un problème, qui est intuitivement la complexité du "meilleur" algorithme possible pour le résoudre, peut être vue comme un "minimum d'un maximum".

Classes de complexité

Certains problèmes sont plus difficiles à résoudre que d’autres, dans le sens où ils nécessitent des algorithmes plus complexes pour être résolus.

Comme je vais vous le montrer aujourd'hui, différentes classes de complexité ont été définies pour décrire la difficulté à résoudre un problème.

Dans cette optique, un problème est dit “polynomial” s’il peut être résolu par un algorithme dont la complexité est asymptotiquement dominée par un polynôme.

Nous avons déjà rencontré beaucoup d'algorithmes polynomiaux dans ce cours, tels que Dijkstra ou le BFS. Ainsi, si nous considérons, par exemple, les problèmes de plus court chemin que ces algorithmes résolvent, ils peuvent être facilement identifiés comme des problèmes polynomiaux, car un algorithme polynomial les résout.

En conséquence, tous ces problèmes appartiennent à la classe de complexité appelée P, qui signifie Polynomial.

Pour d’autres problèmes, il est plus difficile de déterminer leur classe de complexité. C’est le cas du TSP, par exemple. Personne n’a réussi à trouver un algorithme polynomial pour le résoudre, et il y a de fortes suspicions que ce ne soit tout simplement pas possible.

Le TSP appartient donc à une classe de problèmes plus difficiles, appelés problèmes NP pour "Nondeterministic Polynomial". Grosso modo, un problème de décision est un problème NP si l'on peut vérifier "rapidement", avec une complexité polynomiale, si une solution candidate est effectivement une solution.

Sans entrer dans trop de détails, on doit souvent utiliser des algorithmes à complexité exponentielle pour résoudre les problèmes NP.

Une autre classe célèbre de problèmes est celle des problèmes NP-Complets. Les problèmes NP-Complets sont au moins aussi difficiles à résoudre que tous les autres problèmes NP. En d'autres termes, un algorithme qui peut résoudre un problème NP-Complete peut résoudre n'importe quel autre problème NP.

Il suffirait simplement de réécrire l’entrée et de réinterpréter la sortie pour l’adapter au nouveau problème. Ces réécritures peuvent être faites à l’aide d’algorithmes polynomiaux.

Comme vous l'avez peut-être deviné, il a été prouvé que le TSP est un problème NP-Complete.

Mots de conclusion

Ainsi, aujourd’hui je vous ai montré que si vous êtes capable de résoudre le TSP, vous êtes aussi capable de résoudre n’importe quel autre problème NP. D’un point de vue théorique, cela semble intéressant, mais d’un point de vue opérationnel, résoudre le TSP nécessite toujours un algorithme exponentiel, ce qui pour notre jeu de labyrinthe n’est probablement pas idéal. Ne vous découragez pas, car la semaine prochaine nous vous montrerons comment résoudre le problème plus rapidement, à condition que vous acceptiez que la solution ne soit pas nécessairement optimale, mais suffisamment bonne.

Pour aller plus loin

2 — Complexité en espace

Les classes de complexité ci-dessus décrivent les besoins en temps pour résoudre les problèmes. Pour mesurer d’autres besoins, comme la consommation de mémoire, il existe d’autres classes de complexité.

Similaire à la complexité temporelle, la complexité spatiale mesure la plus petite quantité de mémoire qu’un programme aurait besoin pour résoudre le problème considéré, pour l’entrée du pire cas. Là encore, cela peut être vu comme un “minimum d’un maximum”.

Nous utilisons aussi les notations big-O pour décrire l’utilisation de la mémoire, en fonction de la taille de l’entrée. Par exemple, $O(n)$ désigne une utilisation linéaire de la mémoire, et $O(n!)$ indique que résoudre le problème nécessite au moins une quantité de mémoire qui croît de façon factorielle avec la dimension de l’entrée.

Comme pour les classes de complexité temporelle, il existe une énorme taxonomie des classes de complexité spatiale.

Certaines classes de complexité et leurs inclusions (source).

Parmi les classiques, PSPACE indique qu’un problème ne peut pas être résolu avec moins qu’une quantité polynomiale de mémoire.

Les complexités spatiale et temporelle ne sont pas sans lien. Par exemple, il est montré que NP $\subseteq$ PSPACE. Cependant, de nombreuses égalités entre classes sont inconnues, beaucoup d’entre elles étant des problèmes ouverts en recherche depuis des décennies.

Pour aller au-delà

  • Complexity classes.

    Une taxonomie des classes de complexité des fonctions.

  • P = NP ?.

    Le problème de déterminer si P et NP sont identiques est un problème majeur en informatique.