La partie "Complexité" du cours Calculabilité et Complexité démarrera le 13 nov 2023. Nous occuperons la salle 1-Z-61.
Stéphane Le Roux est chargé de TDs.
Le polycopié du
cours est basé sur le polycopié de Serge Haddad auquel nous
avons apporté quelques ajustements.
L'examen final a eu lieu le 15 janvier 2024. Voici le sujet avec son corrigé.
Introduction générale. Modèle de calcul = (N)TM. Complexité en temps et en espace. Thm. 1, 2, 3 & 4 du polycopié.
Réductions logspace entre problèmes et logspace-équivalence. La composition de deux fonctions logspace est logspace. Prop. 1 du polycopié.
Problèmes C-complets pour une classe C.
Thm de Cook: le problème SAT est NP-complet. Prop. 3 du polycopié.
Preuve: on montre que pour tout L ∈ NP, il existe une réduction logspace r_L : x → φ_x telle que x ∈ L ssi φ_x est satisfaisable (φ_x exprime exactement l'existence d'un calcul acceptant de M sur x où M est une machine de Turing non déterministe qui reconnaît L en temps p(n)). Donc L≤SAT.
SUBSET-SUM est NP-complet. Prop. 7 du polycopié.
HAMILTONIAN-CIRCUIT est NP-complet. Prop. 5 du polycopié.
HAMILTONIAN-CYCLE est NP-complet. Prop. 6 du polycopié.
CHEMIN-PONDÉRÉ est NP-complet. Prop. 9 du polycopié.
Ceux qui aiment utiliser leur ordinateur pour résoudre des puzzles mathématiques pouront utilement s'attaquer aux problèmes 201, 249 ou 266 du Project Euler.
Soit p un polynome et R un prédicat calculable en temps polynomial (déterministe). Alors le problème L = { x | ∃ y : |y|≤p(|x|) ∧ R(x,y) } est dans NP (dans cette formulation, y est un témoin de l'appartenance de x à L). Réciproquement, tout problème de NP est la forme { x | ∃ y ... } comme ci-dessus.
GAP, le « Graph Accessibility Problem », est soluble en espace log²(n). Thm de Savitch; NSPACE(f(n))⊆ SPACE(f(n)²) pour toute fonction propre f≥log.
Coro: NPSPACE=PSPACE. Donc aussi coNPSPACE=PSPACE. Thm. 5 du polycopié.
QBF, ou « Quantified Boolean Formula », est PSPACE-complet. Prop. 12 du polycopié.
UReg (Universalité pour les expressions régulières) est PSPACE-complet. Props. 13 & 14 du polycopié.
HORNSAT est une version de SAT où on se restreint à des (conjonctions de) clauses ne contenant chacune qu'au plus un littéral positif. Alors HORNSAT est décidable en temps polynomial. Par ailleurs HORNSAT est PTIME-difficile, donc PTIME-complet. HORNSAT ≤ 3HORNSAT donc 3HORNSAT aussi est PTIME-complet. Props. 15 & 16 du polycopié.
BinOp demande, pour une loi binaire (G,⋅) si un élément g∈G donné est obtenable en combinant des éléments de H⊆G (répétitions permises). BinOp ∈ PTIME et 3HORNSAT ≤ co-BinOp. Donc BinOp (et co-BinOp) sont PTIME-complets. Prop. 19 du polycopié.
CNF-Vacuity (décider si une grammaire hors-contexte définit un langage vide ou non) est PTIME-complet. Props. 22 & 23 du polycopié.
CIRCUIT-VALUE est PTIME-complet. Props. 24 & 25 du polycopié.
GAP est NL-complet. Props. 26 & 27 du polycopié.
Thm d'Immerman-Szelepscéznyi: coGAP ∈ NL: Il existe un algorithme non-déterministe en espace logarithmique qui vérifie qu'un sommet donné t n'est pas atteignable depuis un sommet donné s dans un graphe orienté G. On admet ce résultat mais les esprits curieux trouveront l'algorithme dans le polycopié.
Coro: NL=coNL. Coro 3 du polycopié.
co2SAT∈NL et coGAP≤2SAT. Coro: 2SAT est NL-complet.