Preuve vérifiable de manière probabiliste

En théorie de la complexité, une preuve vérifiable de manière probabiliste[1] aussi appelée preuve vérifiable en probabilité[2] ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] réfère à l'ensemble des problèmes de décision qui ont des preuves vérifiables en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours acceptée ; une preuve incorrecte est rejetée avec une probabilité supérieure ou égale à 1/2.

Lien avec les classes de complexité usuelles

On obtient les classes de complexité usuelles avec des valeurs extrêmes pour r(n) et/ou q(n) :

• PCP[0, 0] = P, car P n'utilise pas d'aléatoire et n'a pas d'accès à une quelconque preuve.
• PCP[O(log(n)), 0] = P, car un nombre logarithmique de bits aléatoires n'aide pas une machine polynomiale, il est toujours possible d'essayer toutes les suites de bits de longueur logarithmique en temps polynomial.
• PCP[0,O(log(n))] = P, car sans aléatoire, la preuve est juste une suite de bits de longueur logarithmique. On peut les essayer toutes en temps polynomiale.
• PCP[poly(n), 0] = coRP, car avec de l'aléatoire, et pas d'accès à une quelconque preuve, cela revient à accepter toutes les instances positives, et à faire peu d'erreur sur les instances négatives (le dual de la classe RP)
• PCP[0, poly(n)] = NP (car pour NP, on peut vérifier une preuve entière, de longueur polynomiale et sans aléatoire).

Théorème PCP

De manière intéressante, le théorème PCP énonce que PCP[O(log n), O (1)] = NP. Autrement dit, un problème est dans NP si l'on peut vérifier des preuves en temps polynomial en utilisant un nombre logarithmique de bits aléatoires et un nombre constant de bits de la preuve.

Notes et références

1. Sylvain Perifel, Complexité algorithmique, p. 283
2. Bernard H. Korte et Jens Vygens (trad. Jean Fonlupt et Alexandre Skoda), Optimisation combinatoire : Théorie et algorithmes, Springer-Verlag, 2010 (lire en ligne), p. 443