Complexité / L3 / année 2024-25

Organisation du cours

La partie "Complexité" du cours Calculabilité et Complexité démarrera le 18 nov 2024. Nous occuperons la salle 1-Z-61.

Guillaume Sceri est chargé de TDs.

Le [[pdf|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 13 janvier 2025. Voici le [[pdf|sujet avec un corrigé possible]].

Contenu des cours

1 (18 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 (25 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&eacute.

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 (2 déc)

SUBSET-SUM est NP-complet. Prop. 7 du polycopi&eacute.

HAMILTONIAN-CIRCUIT est NP-complet. Prop. 5 du polycopi&eacute.

HAMILTONIAN-CYCLE est NP-complet. Prop. 6 du polycopi&eacute.

CHEMIN-PONDÉRÉ est NP-complet. Prop. 9 du polycopi&eacute.

Ceux qui aiment utiliser leur ordinateur pour résoudre des puzzles athématiques pouront utilement s'attaquer aux problèmes 201, 249 ou au #266 du Project Euler.

Lem. 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, on dit que 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 (pour un certain polynome p et un certain prédicat R dans PTIME).

4 (9 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é.

UnivReg (Universalité pour les expressions régulières) est PSPACE-complet. Props. 13 & 14 du polycopié.

5 (16 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&eacute.

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&eacute.

CIRCUIT-VALUE est PTIME-complet. Props. 24 & 25 du polycopi&eacute. 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.

6 (6 jan)

GAP est NL-complet. Props. 26 & 27 du polycopié.

Thm d'Immerman-Szelepcsényi: coGAP ∈ NL. (L'algo vu en cours est plus simple que l'algo 13 du polycopi&eacute qui s'intéresse lui au graphe des configurations d'une machine logspace non-déterministe mais l'esprit est le même.)

Coro: NL=coNL. Coro 3 du polycopié.

Thm: 2SAT est NL-complet. On montre coGAP≤2SAT (facile) et 2SAT∈NL (moins facile). Les preuves se trouvent dans le corrigé de l'examen de janvier 2022.

Examens des années précédentes

Voici les sujets soumis ces dernières années. Je propose aussi des 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é.