Théorème PCP

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Problème de correspondance de Post.

En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP 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és 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. L'abréviation PCP est l'acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité »[1].

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[modifier | modifier le code]

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 cette preuve P’ (à l'aide d'un algorithme randomisé) pour être convaincu de l'exactitude de la preuve à 99%.

« Le coup de la confiture »[modifier | modifier le code]

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, dit-elle, 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. »

Le modèle[modifier | modifier le code]

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 de 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 en probabilité.

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'autre termes, le vérificateur ne rejette pas 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 une 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 la possibilité de voir les systèmes PCP comme une généralisation possible de NP. Au lieu d'effectuer un calcul en temps polynomial à la réception de la preuve complète (comme dans le cas 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 très longues preuves, en ne regardant pas plus qu'un nombre polynomial d'emplacements, ou de manière équivalente de ne regarder que très peu de bits d'une preuve possible.

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é 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].

L'énoncé[modifier | modifier le code]

Les preuves vérifiables en probabilité donnent naissance à de nombreuses 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, qui est un résultat majeur de la théorie de la complexité informatique, énonce que

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

Application aux algorithmes d'approximation[modifier | modifier le code]

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.

L'exemple de MAX-3SAT[modifier | modifier le code]

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

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.

Importance et histoire[modifier | modifier le code]

Ingo Wegener[6] a dit a 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[7], c'est « l'aboutissement une série de travaux impressionnants, riches en innovations ».

En 2001, Sanjeev Arora, Uriel Feige (en), Shafi Goldwasser, Carsten Lund (en), 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)[8].

En 2006, Irit Dinur a publié une preuve complètement nouvelle du théorème[9], combinatoire, utilisant notamment les graphes expanseurs (Dinur 2007).

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

  • 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, no 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, no 1,‎ 1998, p. 70–122 (DOI 10.1145/273865.273901, lire en ligne)
  • 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, no 3,‎ 1998, p. 501–555 (DOI 10.1145/278298.278306, lire en ligne)

Vulgarisation[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]

(en) La classe PCP sur le Complexity Zoo

Notes et références[modifier | modifier le code]

  1. 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
  2. La conférence plénière d'Init Dinur est accessible sur sa page personnelle, à l'adresse Probabilistically Checkable Proofs (survey and talk).
  3. Dans les termes du compte-rendu paru dans (Ghys 2010).
  4. Christian Scheideler, « Computational Models » (consulté le 16 juillet 2013).
  5. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7), chap. 11.2.2 (« PCP and hardness of approximation »)
  6. « The most important result in complexity theory since Cook's Theorem » dans : (en) Ingo Wegener, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer,‎ 2005 (ISBN 978-3-540-21045-0, lire en ligne), p. 161.
  7. « A culmination of a sequence of impressive works [...] rich in innovative ideas » dans : (en) Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press,‎ 2008 (ISBN 978-0-521-88473-0, lire en ligne), p. 405.
  8. Page officielle du prix Gödel 2001
  9. Page du prix Gödel 2009, pour le produit zig-zag de graphes, dont le dernier paragraphe porte sur la preuve de Dinur