Skip to content. | Skip to navigation

Personal tools

Sections

Consider the world interacting

  • Logo CNRS
  • Logo ENSL
  • logo-enssib.jpg
You are here: Home / Agenda / Seminars / Séminaires 2011 / Hasard, complexité et preuves : le théorème PCP

Hasard, complexité et preuves : le théorème PCP

Hasard, complexité et preuves : le théorème PCP
When Feb 24, 2011 10:00 to
Feb 25, 2011 04:00
Where Salle de séminaire de l’IXXI
Add event to calendar vCal
iCal

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.

En 4 séances de cours assurées par Nicolas Schabanel (LIAFA & IXXI) et réparties sur deux jours, une démonstration complète de ce théorème vous sera présentée. 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é.

Un volume de 4x2h de cours est prévu 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.

Programme détaillé

Jeudi 24 février

  • 10h-12h : 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.
  • 14h-16h : Test de linéarité et auto-correction (suite), NP est dans PCP(poly(n), 1).

Vendredi 25 février

  • 10h-12h : Définition et résultats préliminaires sur les graphes expandeurs (admis), Premières étapes de la preuve de Dinur.
  • 14h-16h : Amplification du Gap et conclusion du théorème PCP.