La partie "Complexité" du cours Calculabilité et Complexité démarrera le 3 nov 2025. Nous occuperons la salle 1-Z-61.
Luc Lapointe 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, lundi 12 janvier 2026 de 10h45 à 12h45, prendra la forme d'un devoir sur table (documents interdits) en salle 1-Y-40.
Introduction générale. Modèle de calcul = (N)TM. Complexité en temps et en espace. Thm. 1, 2 & 3 du polycopié.
Thm. 4 du polycopié.
Réductions logspace entre problèmes et logspace-équivalence.
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 pourront utilement s'attaquer au #266 du Project Euler.
Thm. Soit p un polynome et R un prédicat calculable en temps polynomial (déterministe). Alors le problème L = { x∈A* | ∃ y∈B* : |y|≤p(|x|) ∧ R(x,y) } est dans NP (dans cette formulation, on dit que y est un témoin de l'appartenance de x à L). Réciproquement, tout problème de NP est de la forme { x | ∃ y ... } comme ci-dessus (pour un certain polynome p et un certain prédicat R dans PTIME).
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é.
UnivReg (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é. Le problème est PTIME-complet même si on se restreint à des portes ET/OU (MONOTONE CIRCUIT-VALUE) ou même seulement à des portes NAND.
NL est le nom abrégé pour NSPACE(log n). GAP est dans NL. Prop. 26 du polycopié.
Thm d'Immerman-Szelepcsényi: coGAP aussi est dans NL. Prop. 26 du polycopié. (L'algo vu en cours est plus simple que l'algo 13 du polycopié qui s'intéresse lui au graphe des configurations d'une machine logspace non-déterministe mais l'esprit est le même.)
GAP est NL-difficile, donc NL-complet. Prop. 27 du polycopié.
Coro: NL=coNL. Coro 3 du polycopié.
Thm: 2SAT est NL-complet. On montre coGAP≤2SAT (facile) et 2SAT∈coNL (moins facile), donc 2SAT∈NL.
Plan de preuve pour 2SAT∈coNL: à φ on associe son graphe des implications Gφ. Ses sommets sont tous les littéraux et chaque clause ℓ∨ℓ' de φ donne lieu à deux arêtes (¬ℓ)→ℓ' ainsi que (¬ℓ')→ℓ. On montre alors que φ n'est pas satisfaisable ssi il existe une variable x telle que Gφ contient un circuit x→*→(¬x)→*→x. Plus de détails dans wikipedia.
Notez qu'il n'y aura pas cours le 5 janvier mais qu'il y aura bien TD (préparation à l'examen) le 8 janvier.
Voici les sujets d'examen proposés ces dernières années ainsi que leurs corrigés. Notons qu’on ne se prépare pas bien en consultant un corrigé pour une question sur laquelle on n’a pas vraiment réfléchi. L’intérêt du corrigé est d’une part de vous permettre de vérifier que votre réponse est correcte et complète, d’autre part de voir quel est le niveau de détail (ou plutôt le niveau d’abstraction) attendu dans vos réponses en situation de devoir sur table en temps limité.