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.
Écris le tout premier commentaire