Complexité / L3 / année 2021-22

Ph. Schnoebelen
LSV, CNRS & ENS Paris-Saclay


Le corrigé de l'examen du 10 janvier est disponible ici

.

Organisation du cours

La partie "Complexité" du cours Calculabilité et Complexité démarrera le lundi 15 nov 2021. Nous occuperons la salle 1Z56 à partir du lundi 22 novembre.

Benjamin Bordais 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 aura lieu le lundi 10 janvier 2022 de 10h45 à 12h45. Il portera uniquement sur la partie « Complexité » du cours. NB: Documents et ordinateurs interdits, y compris vos notes de cours.

Contenu des cours

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

1 (15 nov)

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

2 (22 nov)

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. 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 code l'existence d'un calcul d'une machine qui reconnaît L en NP). Donc L≤SAT. Prop 3 du polycopié.

3 (29 nov)

3SAT est NP-complet.

HAMILTONIAN_CIRCUIT est NP-complet. Prop 5 du polycopié.

HAMILTONIAN_CYCLE, et SUBSET_SUM sont NP-complets. Prop 6, 7 du polycopié.

Il existe un algorithme pseudo polynomial pour SUBSET_SUM. Prop 8 du polycopié.

* (6 déc)

Visite de laboratoire → pas de cours le 6 décembre.

4 (13 déc)

GAP, le « Graph Accessibility Problem », est soluble en espace log²(n). Thm de Savitch; NSPACE(f(n))⊆ SPACE(f(n)²) pour f≥log space-constructible.

Coro: NPSPACE=PSPACE. Thm 5 du polycopié.

QBF, ou « Quantified Boolean Formula », est PSPACE-complet. Prop 12 du polycopié.

GAP est NL-complet. Prop 26 et 27 du polycopié.

5 (3 jan)

HORNSAT et 3HORNSAT sont PTIME-complets. Prop 15 et 16 du polycopié.

CIRCUIT-VALUE est PTIME-complet, même si on se restreint à des portes ET/OU (MONOTONE CIRCUIT-VALUE) ou même seulement à des portes NAND. Prop 24 et 25 du polycopié.

Thm d'Immerman-Szelepscéznyi: coGAP ∈ NL. Coro: NL=coNL. Coro 3 du polycopié.

co2SAT∈NL et coGAP≤2SAT. Coro: 2SAT est NL-complet.

Examens des années précédentes

À propos du LSV