Méthode de démonstration NP-complétude

Pour prouver qu’un problème $Q$ est NP-complet, il faut démontrer deux points.

Étapes de la preuve

1. Montrer que $Q\in$ NP

Trouver :

• Un Certificat de verification de taille polynomiale
• Un algorithme de vérification en temps polynomial

2. Montrer que $Q$ est NP-difficile

Choisir un problème $Q^{\prime }$ déjà connu comme NP-complet et construire une Réduction polynomiale :

$Q^{\prime }{\ll }_{P}Q$

Problèmes de référence courants

Problème de base

• SAT (théorème de Cook, 1972)

Problèmes souvent utilisés comme source

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

Exemple : Prouver que Vertex Cover (VC) est NP-complet

Étape 1 : VC $\in$ NP

• Certificat : Ensemble $C\subseteq V$
• Vérification : Vérifier que $|C|\le k$ et que toute arête a au moins une extrémité dans $C$

Étape 2 : Stable maximum (MIS) ${\ll }_P$ VC

Transformation :

$f:⟨G=(V,E),k⟩\to ⟨G^{\prime }=G,k^{\prime }=n-k⟩$

Preuve de correction : $S$ est un stable de taille $\ge k$ ssi $V\setminus S$ est une couverture de taille $\le n-k$.

Conclusion

VC est NP-complet.

Propriétés utiles

Transitivité

Si $Q_1{\ll }_P{Q}_2$​ et $Q_2{\ll }_P{Q}_3$​ alors $Q_1{\ll }_P{Q}_3$

Permet de chaîner les réductions.

Théorème

Si $Q$ est NP-complet et $Q{\ll }_P{Q}^{\prime }$ où $Q^{\prime }\in$ NP, alors $Q^{\prime }$ est NP-complet.