Introduction à la complexité

Année 2017-2018

Cours le mardi 9h-11h salle 2018, Sophie Germain.

• Semaine 1 (7/11/2017)
  • Introduction : complexité en temps et en espace (présentation informelle) ; relative indépendance vis-à-vis du modèle de calcul pour des notions suffisament grossières comme le temps polynomial (classe P).
  • Le temps et l'espace de façon informelle, sur quelques exemples : addition et multiplication sur les entiers (algorithmes de l'école primaire), accessibilité dans un graphe (marquage), évaluation d'une expression booléenne, le problème SAT (classe NP).
• Semaine 2 (14/11/2017)
  • Poursuite de l'introduction au temps (ou à l'espace) non déterministe pour un problème du type ∃ x P(x) : une phase de supposition (pour x), puis une phase de vérification déterministe, classe NP (non déterministe polynomiale).
  • Remarque : à partir d'un algorithme en temps polynomial pour la satisfaisabilité des formules propositionnelles, on obtient un algorithme en temps polynomial qui de plus fournit la valuation satisfaisant une formule (quand elle existe).
  • le problème du circuit hamiltonien est dans la classe NP.
  • Un exemple de problème d'optimisation, le problème du voyageur de commerce (TSP, Travel Salesman Problem) ; le problème de décision associé TSP_k (existe-t-il un circuit hamiltonien de coût ≤ k ?) est dans la classe NP ; réduction de TSP_k à TSP et de TSP à TSP_k.
  • Le modèle de calcul : machines de Turing à plusieurs bandes bi-infinies et têtes indépendantes, une bande d'entrée en lecture seule , une bande de sortie en écriture seule, et une ou plusieurs bandes de travail ; fonction d etransition (machine déterministe), relation de transition (machine non déterministe) ; configuration (pour une machine à k bandes, un 2k+1-uple avec l'état de la machine, le contenu de la bande k jusqu'à la position de la tête de lecture (comprise), le contenu de la bande k après la position de la tête de lecture (non comprise).
• Semaine 3 (21/11/2017)
  • Feuille d'exercice
  • Mesures et classes de complexité en temps et en espace : DTIME(f(n)), NTIME(f(n)), DSPACE(f(n)), NSPACE(f(n)) pour f:ℕ → ℕ ; théorème d'accélération linéaire (linear speedup) ; propriétés de clôture : DTIME(f(n)) est close par intersection et réunion finies, ainsi que passage au complémentaire, NTIME(f(n)) est close par intersection et réunion finies.
• Semaine 4 (28/11/2017)
  • Relation entre temps et espace : NTIME(f(n)) ⊆ DSPACE(f(n)), pour f(n) ≥ log₂ NSPACE(f(n)) ⊆ DTIME(2^O(f(n))).
  • Classes de complexité L, NL, P, NP, PSPACE, NPSPACE, EXPTIME, et relations d'inclusion se déduisant des deux résultats précédents.
  • TD le mercredi 29/11/2017 8:30-10:30 en salle 1004 SG
• Semaine 5 (5/12/2017)
  • Résultats négatifs : "Gap theorem", théorèmes de hiérarchie en temps et en espace, conséquence : P ⊊ EXPTIME, NL ⊊ NPSPACE
  • Les classes P et NP : la caractérisation de la semaine 2 (précisée) est bien équivalente à celle utilisant les machines non déterministes ; réduction en temps polynomial (et réduction en espace logarithmique) ; problèmes NP-difficiles, NP-complets ; théorème de Cook (Cook 1971, Levin 1969) : le problème de la satisfaisabilité des ensembles de clauses est NP-complet ; le problème 3-SAT de la satisfaisabilité des clauses d'au plus 3 littéraux, est NP-complet (exercice).
• Semaine 6 (12/12/2017)
  • Le problème du chemin Hamiltonien (dans le cas des graphes non orientés) est NP-complet par réduction de 3-SAT : principe de la démonstration (variante mineure de Papadimitriou p. 193).
  • La classe P : le problème de la satisfaisabilité des clauses de Horn est P-complet (en reprenant a preuve du théorème de Cook dans ce cas particulier).
  • Complexité en espace : théorème de Savitch PSPACE = NPSPACE ; l'accessibilité dans un graphe est un problème NL-complet.
  • TD le mercredi 13/12/2017 9:00-12:00 en salle 1004 SG

Bibliographie

• Sylvain Perifel, complexité Algorithmique, Ellipses 2014 (disponible en pdf sur sa page à l'irif), premiers chapitres ;
• Christos Papadimitriou, Computational Complexity, Pearson 1993, très introductif (remarque : on sait depuis la parution du livre que le problème de la primalité se résout en temps polynomial, chercher : Algorithme AKS).

dernière modification : mardi 12 décembre 2017 21:35:14 CET