Complexité / L3 / année 2018-19

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

Organisation

La partie "Complexité" du cours Calculabilité et Complexité démarre le 12 nov 2018.

Anthony Lick est chargé de TDs.

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

Le corrigé du DM distribué le 20 déc est maintenant disponible.

L'examen final a eu lieu le lundi 14 janvier de 9h30 à 11h30 en salle C315. Cf corrigé.

Contenu des cours

1 (12 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 (19 nov)

Réductions (logspace ou temps polynomial) entre problèmes. Graphes orientés : logspace-équivalence entre la représentation matricielle et la représentation par liste d'arêtes. Problèmes C-complets pour une classe C. Le problème SAT est dans NP, il est NP-complet (preuve reportée au 26 nov).

3 (26 nov)

Thm de Cook: SAT est NP-difficile. Preuve: on montre que pour tout L ∈ NP, il existe une réduction logspace f_L : x &mapstoright; φ_x telle que x ∈ L ssi φ_x est satisfaisable. Donc L≤SAT. Prop 3 du polycopié. Circuit Hamiltonien est NP-complet. Prop 5 du polycopié.

4 (10 déc)

Cycle Hamiltonien, Subset Sum, et Chemin Pondéré sont NP-complets. Prop 6, 7, 9 du polycopié. Il existe un algorithme pseudo polynomial pour Subset Sum. Prop 8 du polycopié. La composition de deux réductions logspace est logspace.

5 (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 est PSPACE-complet. Prop 12 du polycopié.

6 (20 déc)

GAP est NL-complet.
coGAP est dans NL !! Coro. NL=coNL.

7 (7 janvier)

HORNSAT peut être résolu en temps polynomial. Il est même PTIME-complet. 3HORNSAT ≤ CLB (= Clôture loi binaire). CLB ≤ CIRCUIT-VALUE.

Examens précédents

À propos du LSV