Complexité / L3 / année 2017-18

Complexité (L3)
Ph. Schnoebelen, LSV, CNRS & ENS Paris-Saclay

Organisation

La partie "Complexité" du cours Calculabilité et Complexité démarre le 13 nov 2017 et se termine avec l'examen du 18 janv 2018 (de 15h à 17h). Il y aura un DM à rendre le 20 décembre.

Adrien Koutsos est chargé de TDs.

Le polycopié du cours est basé sur le polycopié de Serge Haddad auquel nous avons apporté quelques ajustements minimes afin de mieux réfléter ce qui est dit en cours.

Contenu des cours

1 (13 nov)

Intro 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 entre problèmes. Problèmes C-complets pour une classe C. Les problèmes SAT et CNF3-SAT sont NP-complets. Prop 2, 3, 4 du polycopié.

3 (27 nov)

CIRCUIT HAMILTONIEN, pour les graphes orientés, et CYCLE HAMILTONIEN, pour les graphes non orientés, sont NP-complets. SACÀDOS est NP-complet. Prop 5, 6, 7 du polycopié.

4 (4 déc)

CHEMIN_PONDÉRÉ est NP-complet. Prop 9 du polycopié. 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é.

5 (11 déc)

QBF est PSPACE-complet. Prop 12 du polycopié.

5 (18 déc)

HORN_SAT et CIRCUIT_VALUE sont P-complets. Prop 16 et 25 du polycopié.

6 (8 jan)

GAP est NL-complet. Thm d'Immerman-Szelepscényi. NL=co-NL.

Examen (18 jan)

Voici le corrigé du sujet d'examen, ainsi que, pour mémoire, celui du DM du 7 décembre.

Examens précédents

À propos du LSV