Séminaire de Daniel Augot et Hugo Delavenne, INRIA, GRACE
Présentation pour des codeurs de la preuve originelle du théorème PCP
Titre
Présentation pour des codeurs de la preuve originelle du théorème PCP
Résumé
En théorie de la complexité algorithmique, le « théorème PCP » énonce « NP=PCP(O(log n,O(1)) ». La classe PCP(r(n),q(n)) est la classe des langages L tels que pour toute instance dans le langage L il existe un preuve π de son appartenance à L, dont sont seulement O(q(n)) bits seront lus, en utilisant O(r(n)) bit d’aléa. La fonction q(n) devra idéalement être très petite devant n, et ainsi on peut se convaincre que une instance est dans le langage avec beaucoup moins de bits que ceux du témoin NP standard. La force du théorème PCP est de montrer que q(n)=O(1) est possible, pour des instances et témoins de taille n aussi grande que voulue.
La preuve originelle, réputée difficile, repose fortement sur les codes correcteurs. De plus le langage et l’utilisation des codes employés sont très différents de la manière standard de considérer les codes.
Dans cet exposé, j’essaierai de donner la preuve originelle de la manière la plus proche du codage algébrique. Je ne parlerai pas des applications cryptographiques du théorème PCP.
Cet exposé sera suivi de deux autres exposés :
- le 12 mars à 14h00 en visioconférence
- le 26 mars sur le campus de La Garde, Bâtiment M salle M005
