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.

Le corrigé du devoir à la maison distribué le 7 décembre est à maintenant disponible. Merci de me signaler (p.ex. par email) toute erreur, typo, etc.

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)

TBA

Examens précédents

À propos du LSV