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.