Loading AI tools
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.
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).
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
