[PCP 1A/5] N. Schabanel - Preuve complète du théorème PCP

PREUVE COMPLÈTE DU THÉORÈME PCP
Cours de 5x2h par Nicolas Schabanel (CNRS - LIAFA, Université Paris Diderot)
%%%%
Mardi 14 juin 14h-16h (Partie A)
• Definition de la classe PCP
• Théorème PCP NP-difficulté d'approximer à une constante
près un problème de satisfaction de contraintes
• Test de linéarité et auto-correction
%%%%%
Résumé:
En 2006, Irit Dinur a proposé une preuve relativement simple,
intuitive et très certainement élégante d'un des théorèmes majeurs de ces
vingt dernière années en informatique: le théorème PCP, c'est-à-dire la
démonstration que NP = PCP (log n, 1), ou encore qu'il suffit de lire un
nombre _constant_ de bits choisis aléatoirement (suivant une distribution
adéquate) d'une solution d'un problème NP pour décider si c'est bien une
solution valide ou non. Ce théorème a permis en particulier d'étendre les
techniques ultra-classiques de NP-difficulté de la résolution exacte de
problème NP à la démonstration de leur inapproximabilité, avec un très
gros succès puisque de très nombreux résultats donnent le facteur
d'approximation exact. Initialement démontré en 1992 avec des méthodes très
complexes, la preuve d'Irit Dinur est particulièrement intuitive et
satisfaisante pour un algorithmicien, puisqu'elle démontre directement
l'inapproximabilité de Max-3SAT en procédant algorithmiquement par
amplification itérative du gap dans la réduction de NP à SAT.

Je vous propose pendant 5 séances de cours, réparties sur deux jours et demi,
de démontrer intégralement ce théorème. Ce sera l'occasion de découvrir et de
pratiquer les techniques issues de l'aléatoire maintenant classiques en
théorie de la complexité. Nous verrons également les liens étonnants entre
preuve, hasard et inapproximabilité.

J'ai prévu un volume de 5x2h de cours pour cette démonstration. Les
prérequis sont minimes: définition de NP, quelques connaissance de base de
probabilités et de graphes. Les cours seront fait au tableau.