Théorème PCP

En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive. Plus précisément, NP est la classe des problèmes de décision qui ont des preuves pouvant être vérifiées de façon probabiliste en ayant accès à un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits aléatoires.

Le théorème PCP est très important en informatique théorique : il apporte notamment de nombreux résultats sur la difficulté d'approximer les problèmes algorithmiques.

Présentation informelle

Le théorème PCP affirme que, si l'on tolère une marge d'erreur, il est inutile de lire une démonstration en entier pour être convaincu de sa correction. On peut reformuler cette affirmation aussi comme suit : il existe une constante K telle que toute preuve mathématique P de longueur n peut être réécrite en une preuve P’ de longueur polynomiale en n, de sorte qu'il suffise d'examiner seulement K symboles de P’ (à l'aide d'un algorithme randomisé) pour être convaincu de l'exactitude de la preuve à 99 %.

« Le coup de la confiture »

Irit Dinur

Considérons une tranche de pain avec une goutte de confiture dessus. Il y a peu de chance de trouver la confiture en inspectant un échantillon du morceau de pain. Par contre, en étalant la confiture, on est quasiment sûr d'en trouver en inspectant un échantillon.

Lors de sa conférence plénière au congrès international des mathématiciens de 2010, Irit Dinur a utilisé une analogie pour faire comprendre ce théorème. Elle est rapportée en ces termes par Étienne Ghys :

« C’est un peu comme si vous avez une tranche de pain qui a peut-être quelque part, une petite goutte de confiture, mais vous ne savez pas où. Vous prélevez un bout de la tartine, au hasard, et vous ne trouvez pas de confiture ; pouvez-vous en déduire qu’il n’y a pas de confiture du tout ? Certainement pas, sauf si vous faites beaucoup d’échantillonnages. Mais si vous commencez par étaler la confiture sur la tranche de pain avec un couteau, elle se retrouvera un peu partout et il suffit d’en prendre un échantillon pour savoir s’il y avait ou pas une goutte de confiture. Ici, c’est la même chose. On part d’une preuve P qui possède quelque part, peut-être, une erreur. Il existe une manière d’« étaler » la preuve pour en construire une autre P’ dans laquelle les erreurs, s’il y en a, se sont « propagées » un peu partout et elles sont maintenant faciles à détecter en prenant un tout petit nombre d’échantillons. »

Système PCP

Considérons le problème de vérifier une preuve pour un théorème mathématique. Puisque les preuves peuvent être longues et difficiles à vérifier dans leur intégralité, on peut chercher une façon de présenter une preuve de telle sorte qu'il suffise d'en vérifier une petite partie seulement pour juger la validité du théorème avec un niveau de confiance raisonnablement élevé. Cette question est abordée par des systèmes de preuve vérifiable de manière probabiliste.

De manière informelle, un système de preuve vérifiable en probabilité (PCP) pour un langage est un vérificateur probabiliste en temps polynomial qui a un accès direct aux bits individuels d'un mot binaire. Ce mot, appelé oracle, représente une preuve et ne sera examiné qu'en partie seulement par le vérificateur. Les questions posées à l'oracle sont des positions dans le mot binaire et des tirages à pile ou face qui peuvent éventuellement dépendre des réponses aux requêtes précédentes. C'est le vérificateur qui décide si une entrée donnée appartient au langage. Si l'entrée est dans le langage, on demande que le vérificateur accepte toujours le mot, pourvu qu'on lui fournisse un oracle adéquat. En d'autres termes, le vérificateur ne rejette jamais un mot qui est dans le langage. Sinon, si le mot n'est pas dans le langage, le vérificateur le rejette avec une probabilité supérieure à un demi, peu importe l'oracle utilisé.

On peut voir les systèmes PCP en termes de systèmes de preuve interactifs. On considère alors l'oracle comme un prouveur (qui veut prouver l'énoncé), et les questions comme autant de messages qui lui sont envoyés par le vérificateur. Dans le cadre de la PCP, le prouveur est vu comme étant sans mémoire des questions précédentes, et ne tient donc pas compte, dans ses réponses, des questions posées précédemment.

Une interprétation plus intéressante est de voir les systèmes PCP comme une généralisation des vérificateurs pour la classe NP. Au lieu d'effectuer un calcul en temps polynomial à la réception de la preuve complète (comme dans le cas d'un vérificateur pour un problème de NP), on permet au vérificateur d'effectuer des tirages à pile ou face et d'examiner la preuve seulement aux emplacements de son choix. Ceci lui permet d'inspecter de longues preuves, en ne regardant pas plus qu'un certain nombre polynomial d'emplacements, ou de manière équivalente de ne regarder que très peu de bits d'une preuve.

Il est remarquable que les systèmes PCP permettent de caractériser entièrement les langages dans NP. Cette caractérisation s'est révélée utile par la connexion établie entre la difficulté d'approximation de quelques problèmes NP-difficiles et la question de l'égalité entre P et NP. Autrement dit, des résultats de non approximabilité pour divers problèmes d'optimisation classiques ont été établis en utilisant des systèmes PCP pour des langages de la classe NP.

Énoncé

Les preuves vérifiables en probabilité donnent naissance à des classes de complexité selon le nombre de questions exigées et la quantité d'aléatoire utilisé. 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 probabilité qui peuvent être vérifiées en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Comme déjà dit plus haut, les preuves correctes doivent toujours être acceptées et des preuves incorrectes doivent être rejetées avec une probabilité d'au moins 1/2. Le théorème PCP énonce que

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

Démonstration

Une démonstration d'un résultat plus faible, NP = PCP[n³, 1], est donnée dans un des cours de Dexter Kozen.

Application aux algorithmes d'approximation

Le théorème PCP a des conséquences importantes dans le domaine des algorithmes d'approximation. En particulier, il sert à montrer que les problèmes MAX-3SAT et Maximum Independent Set entre autres, ne peuvent pas être approximés efficacement, sauf si P=NP.

Exemple de MAX-3SAT

Le problème MAX-3SAT est le suivant : étant donné une formule 3CNF, c'est-à-dire en forme normale conjonctive, dont chaque clause contient au plus 3 littéraux (comme dans le problème 3-SAT), quel est le nombre maximum de clauses pouvant être satisfaites par la même affectation des variables ?

Le résultat de difficulté d'approximation est le suivant :

Il existe une constante $\rho <1$ telle que l'existence d'un algorithme d'approximation pour MAX-3SAT de rapport d'approximation $\rho$, implique que P = NP.

Ceci est en fait un corollaire du théorème suivant :

Il existe une constante $\rho <1$ telle que pour tout langage $L\in NP$, il existe une fonction $f$ allant des chaînes de caractères vers les formules 3CNF telle que $x\in L$ implique que toutes les clauses de $f(x)$ peuvent être satisfaites, et $x\notin L$ implique que la fraction de clause satisfiables de $f(x)$ est inférieure à $\rho$.

Historique et importance

L'histoire du théorème commence dans les années 1980, avec des travaux sur les preuves à divulgation nulle de connaissance (zero knowledge proof) par Goldwasser, Micali, et Rackoff. Ces résultats n'ont a priori rien à voir avec l'approximation, mais introduisent l'idée de prouveur et de vérificateur. Le lien entre la vérification de preuve et l'approximation est fait au début des années 1990, par Feige, Goldwasser, Lovász, Safra et Szegedy.

En 2001, Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan et Mario Szegedy ont reçu le prestigieux prix Gödel pour leurs articles sur le théorème PCP (Feige et al. 1996) (Arora et Safra 1998) (Arora et al. 1998).

En 2006, Irit Dinur a publié une preuve complètement nouvelle du théorème, combinatoire, utilisant notamment les graphes expanseurs (Dinur 2007). Cette preuve lui a valu le prix Gödel 2019.

Ingo Wegener a dit à propos de ce théorème qu'il était « le résultat le plus important en théorie de la complexité depuis le théorème de Cook ». Pour Oded Goldreich, c'est « l'aboutissement d'une série de travaux impressionnants, riches en innovations ».

Bibliographie

Articles

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra et Mario Szegedy, « Interactive proofs and the hardness of approximating cliques », Journal of the ACM, vol. 43, n^o 2,‎ 1996, p. 268–292 (DOI 10.1145/226643.226652, lire en ligne)

• Sanjeev Arora et Shmuel Safra, « Probabilistic checking of proofs: a new characterization of NP », Journal of the ACM, vol. 45, n^o 1,‎ 1998, p. 70–122 (DOI 10.1145/273865.273901, lire en ligne [archive du 10 juin 2011])

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan et Mario Szegedy, « Proof verification and the hardness of approximation problems », Journal of the ACM, vol. 45, n^o 3,‎ 1998, p. 501–555 (DOI 10.1145/278298.278306, lire en ligne)

• Irit Dinur, « The PCP theorem by gap amplification », Journal of the ACM, vol. 54, n^o 3,‎ 2007, p. 12 (DOI 10.1145/1236457.1236459)

Vulgarisation

• Étienne Ghys, « Vérifier une preuve : la conférence de Irit Dinur », Images des Mathématiques,‎ 2010 (lire en ligne)

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 11 (« PCP Theorem and Hardness of Approximation: An introduction »)

• Dana Moshkovitz, « The tale of the PCP theorem », ACM Crossroads, vol. 18, n^o 3,‎ 2012, p. 23-26 (lire en ligne)

Liens externes

(en) La classe PCP sur le Complexity Zoo