Advertising Console

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

    Repost
    Nicolas Schabanel

    par Nicolas Schabanel

    26
    236 vues
    PREUVE COMPLÈTE DU THÉORÈME PCP
    Cours de 5x2h par Nicolas Schabanel (CNRS - LIAFA, Université Paris Diderot)
    %%%%
    Mercredi 15 juin 10h-12h (Partie A)
    • Test de linéarité et auto-correction (suite)
    • NP est dans PCP(poly(n), 1)
    %%%%%
    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.