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?? (horaire à confirmer), prendra la forme d'un devoir sur table (documents interdits).
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).
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é.