Teorema PCP (Probabilistically checkable proof – Dovada verificabilă probabilistic)

Teorema PCP, numită și teorema caracterizării PCP, este unul dintre rezultatele fundamentale ale teoriei complexității computaționale. Inițialele PCP provin din expresia engleză Probabilistically Checkable Proof, adică „dovadă verificabilă probabilistic”. Ideea centrală este surprinzătoare: orice problemă din clasa de complexitate NP (nondeterministic polynomial time – timp polinomial nedeterminist) poate avea o dovadă reformulată astfel încât corectitudinea ei să poată fi verificată cu o probabilitate foarte mare prin citirea unui număr foarte mic și constant de fragmente ale dovezii. Verificatorul utilizează un număr de biți aleatori proporțional cu logaritmul dimensiunii problemei, fără a fi necesar să citească întreaga demonstrație.

În mod obișnuit, pentru a verifica o demonstrație trebuie examinată întreaga sa succesiune de pași. Teorema PCP arată însă că o demonstrație pentru o afirmație de lungime (n) poate fi transformată într-o altă demonstrație, de lungime polinomială în raport cu (n), care conține suficientă redundanță și structură pentru a permite verificări locale. Un algoritm probabilistic poate alege aleatoriu câteva poziții din această demonstrație și poate decide, cu o precizie foarte mare – de exemplu 99% –, dacă ea este corectă. Numărul pozițiilor examinate nu crește odată cu lungimea dovezii, fiind limitat de o constantă universală.

Formularea matematică a teoremei este:

NP = PCP[O(log n),O(1)].

Aici, O(logn) reprezintă numărul de biți aleatori folosiți de verificator, iar O(1) indică faptul că acesta citește numai un număr constant de biți ai dovezii. Pentru o demonstrație corectă, verificatorul acceptă întotdeauna rezultatul. Pentru una incorectă, el o respinge cu o probabilitate de cel puțin (1/2). Probabilitatea de eroare poate fi redusă prin repetarea verificării. Alegerea porțiunilor examinate este neadaptivă: ea depinde numai de problema analizată și de biții aleatori, nu de conținutul porțiunilor deja citite.

Importanța majoră a teoremei PCP provine din legătura sa cu dificultatea aproximării. Pentru numeroase probleme de optimizare NP-dificile nu este realist să se caute întotdeauna soluția exactă, motiv pentru care se utilizează algoritmi de aproximare. Teorema PCP arată că, pentru anumite probleme, chiar și obținerea eficientă a unei soluții suficient de apropiate de cea optimă este imposibilă, dacă presupunem că P ≠ NP. Astfel, ea nu afirmă numai că anumite soluții exacte sunt greu de calculat, ci stabilește și limite precise asupra calității aproximărilor care pot fi obținute eficient.

O formulare alternativă folosește probleme de satisfacere a constrângerilor, sau CSP. Se poate construi un sistem de constrângeri pentru care este NP-dificil să se distingă între două situații: fie toate constrângerile pot fi satisfăcute simultan, fie nicio atribuire de valori nu poate satisface mai mult decât o anumită fracțiune constantă a acestora. Fiecare verificare locală a unei dovezi PCP poate fi interpretată drept testarea uneia dintre aceste constrângeri. Prin diferite reduceri matematice, această proprietate conduce la rezultate de neaproximabilitate pentru probleme precum satisfacerea unui număr maxim de clauze booleene, găsirea unei mulțimi independente maxime într-un graf sau determinarea celui mai scurt vector dintr-o rețea matematică.

Teorema este rezultatul unei lungi evoluții a cercetărilor asupra demonstrațiilor interactive și probabilistice. Primele rezultate importante au fost obținute în jurul anului 1990 de László Babai, Lance Fortnow și Carsten Lund, fiind dezvoltate ulterior de numeroși cercetători. Forma consacrată a teoremei a fost demonstrată prin contribuțiile lui Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan și Mario Szegedy, publicate în 1998, împreună cu lucrările conexe ale lui Shmuel Safra și ale altor specialiști. Cercetările privind teorema PCP și dificultatea aproximării au fost recompensate cu Premiul Gödel în 2001. În 2005, Irit Dinur a găsit o demonstrație considerabil mai simplă, bazată pe amplificarea diferenței dintre cazurile corecte și incorecte și pe utilizarea grafurilor expandor; această contribuție i-a adus Premiul Gödel în 2019.

Articolul menționează și încercările de construire a unor analogi cuantici ai teoremei PCP. Aceștia privesc dificultatea aproximării valorii jocurilor cuantice nelocale sau a energiei fundamentale a hamiltonienilor cuantici locali. Deși au fost obținute rezultate importante, inclusiv demonstrarea în 2022 a conjecturii NLTS, o formă generală a teoremei PCP cuantice continuă să reprezinte o problemă majoră a teoriei complexității cuantice. În ansamblu, teorema PCP stabilește o legătură profundă între verificarea probabilistică a demonstrațiilor și limitele algoritmilor de aproximare, fiind considerată unul dintre cele mai importante rezultate ale teoriei moderne a complexității.