Théorème PCP

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é[2] une analogie pour faire comprendre ce théorème. Elle est rapportée en ces termes par Étienne Ghys[3] :

« 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. »

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[4].

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.

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[6] :

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

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

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

• 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)

• É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)