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.

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.

Examens précédents

À propos du LSV