Certificat de verification

Un certificat est une preuve qui permet de vérifier rapidement qu’une instance appartient au langage d’un problème de décision.

Définition formelle

Pour un problème $Q\in$ NP, un certificat $c$ est une information de taille polynomiale telle qu’il existe un algorithme $V$ (vérificateur) vérifiant en temps polynomial si $c$ prouve que $x\in Q$.

Exemples

SAT

• Certificat : $P\in \{0,1{\}}^n$ (affectation des variables)
• Vérification : Évaluer toutes les clauses avec cette affectation
• Complexité : $O(n\times m)$

Stable maximum (MIS)

• Certificat : Ensemble de sommets $S\subseteq V$
• Vérification : Vérifier que $|S|\ge k$ et qu’aucune arête ne relie deux sommets de $S$

Hamiltonian Path (HAM)

• Certificat : Permutation $P$ des sommets
• Vérification : Vérifier que chaque paire consécutive forme une arête
• Complexité : $O(n)$