Classe NP

Définition

La classe NP (Nondeterministic Polynomial time) contient les problèmes de décision dont une solution peut être vérifiée en temps polynomial.

$$NP=,Q\mid \exists \text{ veˊrificateur polynomial }V\text{ et certificat }c\text{ tel que }V(x,c)=1⟺x\in Q,$$

On dit aussi qu’un algorithme non déterministe pourrait résoudre $Q$ en temps polynomial en “devinant” le bon certificat.

Exemples

• SAT
• 3-SAT
• Stable maximum (MIS)
• Clique
• Vertex Cover (VC)
• Partition

Relation avec P

$$P\subseteq NP$$

mais la question $P=NP$ ? reste ouverte.

NP-complet et NP-difficile

• Un problème est NP-complet s’il est à la fois dans NP et au moins aussi difficile que tous les autres problèmes de NP (via une Réduction polynomiale).