Relations d'inclusion

Tout problème de $P$ est aussi un problème de $NP$. Ce qui s'écrit aussi

Théorème 10.2.1   $P \subset NP$

Soit $I$ une instance d'un problème $\Pi$ appartenant à $P$, alors il existe un algorithme polynomial permettant de décider $\Pi$. De ce fait, si $I$ est à réponse oui, même un certificat vide permet de le vérifier en temps polynomial.

La question suivante empêche la plupart des chercheurs en informatique de dormir : Est-ce que $P = NP$ ? On sait déjà que $P \subset NP$, pour répondre à la question, il faudrait montrer :

• $NP \subset P$, autrement dit, tout problème de $NP$ peut être résolu en temps polynomial.
• $NP \setminus P \not = \emptyset$, autrement dit, il existe des problèmes de $NP$ qui ne peuvent être résolus en temps polynomial.

Notez que le problème du cycle hamiltonien appartient à $NP$.

• Si $P = NP$, alors il existe un algorithme polynomial permettant de le décider.
• Si $P \not = NP$, alors il convient de se demander si ce problème n'est pas dans $NP \setminus P$, le cas échéant il n'existe aucun algorithme polynomial permettant de le décider.

Etant donné le nombre de problèmes de $NP$ pour lesquels on ne trouve aucun algorithme polynomial, il est fort probable que $P \not = NP$. Notez bien que ceci n'est qu'une conjecture, elle n'est pas démontrée à ce jour.