Complexité / L3 / année 2023-24

Ph. Schnoebelen
LMF, CNRS & ENS Paris-Saclay

 

Organisation du cours

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.

Examen final

L'examen final a eu lieu le 15 janvier 2024. Voici le sujet avec son corrigé.

Contenu des cours

Cette section sera mise à jour à l'issue de chaque cours.

1 (13 nov)

Introduction générale. Modèle de calcul = (N)TM. Complexité en temps et en espace. Thm. 1, 2, 3 & 4 du polycopié.

2 (20 nov)

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.

* (27 nov)

Visite IMAG/Grenoble : pas de cours aujourd'hui.

3 (4 déc)

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.

4 (11 déc)

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é.

5 (18 déc)

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é.

6 (11 jan)

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.

À propos du LSV