Complexité des problèmes & NP-complétude

Bonjour ! Vous êtes de retour ? 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.

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 le résolvent.

Comme nous l’avons vu la semaine dernière, la complexité d’un algorithme inclut une connotation de “pire cas”, car elle mesure le “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”.

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é de résolution d’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é de nombreux 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 cela soit tout simplement impossible.

Le TSP appartient donc à une classe de problèmes plus difficiles, appelés problèmes NP pour “Nondeterministic Polynomial”. En gros, un problème de décision est un problème NP si nous pouvons vérifier “rapidement”, avec une complexité polynomiale, si une solution candidate est effectivement une solution.

Sans entrer dans trop de détails, nous devons souvent utiliser des algorithmes avec une 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 capable de résoudre un problème NP-Complet peut résoudre n’importe quel autre problème NP.

Il suffirait de réécrire les entrées et de réinterpréter les sorties pour les adapter au nouveau problème. Ces réécritures peuvent être effectuées à l’aide d’algorithmes polynomiaux.

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

Ainsi, aujourd’hui, je vous ai montré que si vous êtes capable de résoudre le TSP, vous êtes également 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 encore un algorithme exponentiel, ce qui, pour notre jeu de labyrinthe, n’est probablement pas idéal. Ne vous laissez pas décourager, car la semaine prochaine, nous vous montrerons comment résoudre le problème plus rapidement, à condition d’accepter que la solution ne soit pas nécessairement optimale, mais suffisamment bonne.