Complexité algorithmique

2010-2011

Cours: Patrick Baillot
TD: Bruno Grenet
cours M1 (CB-02) Master IF

à noter:

  • examen: mardi 4/1/2011, 14h-17h, salle B2.


    • Cours
    Horaire: vendredi 10h15-12h15, amphi B.
    Références
    S. Arora, B. Barak. Computational complexity. A modern approach. Cambridge University Press, 2009.
    M. Sipser. Introduction to the theory of computation. 2nd edition. International edition. Course technology, 2006.

    TD
    horaire: mardi 10h15-12h15, salle B2.
    Les feuilles de TD sont disponibles depuis la page de Bruno Grenet.

    Page du cours en 2009-2010.
    Résumés des cours:

  • cours 1 (14/09/2010): Chap. 1: Machines de Turing et complexité en temps. Classe P.
    machines de Turing (MT). fonction calculée par une MT en temps T(n). fonctions constructibles pour le temps. variations sur les MT (alphabet, nombre de bandes, bidirectionnelle) et effet sur le temps. thme de MT universelle efficace (énoncé mais non démontré). classes DTIME(T(n)), FDTIME(T(n)), P, FP.

  • cours 2 (17/09/2010): Chap. 1 (suite)
    codage des MT par des mots de (0,1)^*. démonstration du thme de MT universelle avec simulation en O(T(n)^2) d'une machine de temps T(n). l'existence d'une MT universelle avec simulation avec borne O(T(n)log(T(n)) est admise. la classe FP est close par composition. classe EXP.
    Chap. 2: La classe NP.
    déf. de NP par vérificateur. Exemples de problèmes dans NP (CLIQUE, 0/1IPROG, TSP). P \subseteq NP \subseteq EXP. machines de Turing non déterministes (MTND). classe NTIME(T(n)). caractérisation de NP par MTND.

  • cours 3 (24/09/2010): Chap. 2 (suite)
    démo de NP=Union_c NTIME(n^c). réduction en temps polynomial. problèmes NP-durs et NP-complets. TMSAT est NP-complet. problèmes SAT et k-SAT. Thme de Cook-Levin: SAT NP-complet. démonstration du thme. 3-SAT, CLIQUE, 0/1IPROG, TSP sont NP-complets (énoncé).

  • cours 4 (1/10/2010): Chap. 2 (suite)
    classe des compléments coC, pour une classe C de langages. P \subseteq (NP \cap coNP). caractérisation de coNP avec quantification universelle sur "certificats". langage coNP dur, coNP complet. le langage TAUTOLOGIE est coNP complet. si NP \noteq coNP alors P \noteq NP. si EXP \noteq NEXP alors P \noteq NP (démontré avec technique de padding).
    Chap 3: Diagonalisation
    thme de hiérarchie en temps déterministe: si T, T' constructibles pour le temps et T(n)logT(n)=o(T'(n)), alors il existe L dans DTIME(T'(n)) qui n'appartient pas à DTIME(T(n)). démonstration de ce thme. application: P \neq EXP. thme de Ladner: si P\neq NP, alors il existe L dans NP\P, non NP complet. début de la démonstration.

  • cours 5 (8/10/2010): Chap. 3 (suite)
    fin de la dém. du thme de Ladner. MT et MTND à oracle. classes P^A, NP^A. si A appartient à P, alors P ^A= P. E= { < a, x , 1^n > / la machine M_a accepte x en temps au plus 2^n }; alors P^E= NP^E= EXP. thme de Baker-Gill-Solovay: il existe A, B tels que P^A=NP^A , et P^B=\noteq NP^B. démo du thme.

  • cours 6 (15/10/2010): Chap. 4: Complexité en espace.
    classes SPACE(S(n)) et NSPACE(S(n)). Fonction constructible pour l'espace. Prop: DTIME(S(n)) \subseteq SPACE(S(n)) \subseteq NSPACE(S(n)) \subseteq DTIME(2 ^{O(S(n))}). graphe des configurations G_{M,x} de M sur l'entrée x. déf. de PSPACE, NPSPACE, L, NL. NP \subseteq PSPACE. PATH appartient à NL. L \subseteq NL \subseteq P. Thme de hiérarchie en espace déterministe: si S, S' constructibles pour l'espace et S(n)=o(S'(n)), alors SPACE(S(n)) \subsetnoteq SPACE(S'(n)). langage PSPACE dur, PSPACE complet. SPACE_TMSAT={ < a, x, 1^n > / M_a accepte x en espace n} est PSPACE-complet. déf. de formule booléenne quantifiée (QBF). TQBF={formules QBF vraies}. Thme (Stockmeyer et Meyer): TQBF est PSPACE-complet. Démo du thme. NPSPACE=PSPACE.

  • vendredi 5/11/2010: Partiel, 10h15-12h15. sujet du partiel ( in english ). Une correction.

  • cours 7 (12/11/2010): Chap. 4 (suite)
    Thme de Savitch: NSPACE(S(n))\subseteq SPACE(S(n)^2). fonction implicitement logspace. réduction logspace. NL-complétude. les fonctions implicitement logspace sont préservées par composition. PATH est NL-complet. langage noPATH. noPATHest coNL complet. Thme: NL=coNL. Thme: NSPACE(S)=coNSPACE(S).
    Chap 5: La hiérarchie polynomiale.
    Def. de \Sigma_i, \Pi_i avec quantificateurs et machine déterministe de temps polynomial. Déf. de la hiérarchie polynomiale PH.

  • cours 8 (16/11/2010): Chap. 5 (suite)
    Prop. d'effondrement : Si \Pi_i \subseteq \Sigma_i alors la hiérarchie s'effondre au niveau i. PH\subseteq PSPACE. Déf. de \Sigma_i complétude. \Sigma_iSAT est \Sigma_i-complet. S'il existe un langage PH-complet alors la hiérarchie s'effondre.
    machines de Turing alternantes (MTA). classes ATIME(T(n)), \Sigma_iTIME(T(n)), \Pi_iTIME(T(n)), AP. Thme: \Sigma_i=\cup_c \Sigma_iTIME(n^c), et analogue pour \Pi_i. Thme: AP=PSPACE.
    - machines à oracle et PH: Thme: pour i\geq 1, \Sigma_{i+1}= NP^{\Sigma_i SAT} (et \Sigma_{i+1}= NP^{\Pi_i SAT}).
    Chap 6: Circuits booléens.
    déf. de circuit booléen, taille, profondeur, évaluation sur une valeur de {0,1}^n.

  • cours 9 (26/11/2010): Chap. 6 (suite)
    classes SIZE(T(n)), P/poly. Thme: P\subseteq P/poly. Tout langage unaire est dans P/poly. P/poly contient des langages indécidables. P\noteq P/poly. démonstration de P\subseteq P/poly. Encodage d'un circuit par un mot. Le problème d'évaluation de circuit CIRCUIT_SAT est NP-complet. Familles de circuits P-uniformes, logspace-uniformes.

  • cours 10 (3/12/2010): Chap. 6 (suite)
    Thme: un langage est dans P ssi il est décidé par une famille de circuits P-uniforme (resp. logspace-uniforme). Machines de Turing avec conseil. Classes DTIME(T(n))/a(n). Caractérisation de P/poly avec les machines avec conseil. Thme de Karp-Lipton: si NP \subseteq P/poly, alors PH=\Sigma_2.
    Classes NC^i et NC (on prend la version logspace-uniforme, que je note NC^i). NC \subseteq P. Thme: NC^1 \subseteq L. NL \subseteq NC^2 (admis).
    Chap 7: Classes de complexité probabilistes.
    Machine de Turing probabiliste (MTP). Déf. des classes BPTIME(T(n)), BPP. P\subseteq BPP. Caractérisation alternative de BPP utilisant une machine déterministe de temps polynomial. BPP\subseteq EXP. BPP=coBPP.

  • cours 11 (14/12/2010):
    Chap 7: suite.
    Déf. de RP, coRP. RP \subseteq NP. Déf. de ZPP. ZPP=RP inter coRP. Thme de réduction des erreurs pour BPP. Simulation de tirage de pièce de proba r avec tirage de pièce de proba 1/2, et réciproque. BPP\subseteq P/poly. BPP \subseteq \Sigma_2 inter \Pi_2.

  • cours 12 (17/12/2010):
    Chap 7: suite.
    Fin de la démonstration de BPP \subseteq \Sigma_2 inter \Pi_2.
    Chap 8: Complexité implicite.
    Classe BC (Bellantoni-Cook) des fonctions récursives sûres sur les mots binaires. Les fonctions de BC sont exactement les fonctions de FP.


    • Quelques liens:

  • page wikipedia sur le problème P vs NP.
  • the complexity zoo : un panorama des classes de complexité connues et de leurs liens.