Complexité / L3 / année 2020-21

Ph. Schnoebelen
LSV, CNRS & ENS Paris-Saclay

La partie "complexité" du cours démarre le lundi 16 novembre 2020. Pour le moment, l'épidémie de covid et les règles de confinement nous obligent à faire de l'enseignement à distance et j'utiliserai la session L3 Info sur BlackoardCollaborate.

L'examen final est maintenant disponible ici. Il s'agit d'un devoir à la maison, distribué le mardi 12 janvier et à rendre au plus tard le 26 janvier à 21h00.

Organisation du cours

La partie "Complexité" du cours Calculabilité et Complexité démarre le 16 nov 2020. Benjamin Bordais est chargé de TDs.

Le polycopié du cours est basé sur le polycopié de Serge Haddad auquel nous avons apporté quelques ajustements.

Contenu des cours

1 (16 nov)

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

Cf. transparents.

2 (23 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é.

Cf. transparents.

3 (30 nov)

3SAT est NP-complet.

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

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

Soit p un polynome et R un prédicat calculable en temps polynomial. Alors le problème L = { x | ∃ y : |y|≤p(|x|) ∧ R(x,y) } est dans NP.

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

Cf. transparents.

4 (7 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é.

L'universalité des expressions reégulières est PSPACE-complet. Prop 13 du polycopié.

Cf. transparents.

5 (14 déc)

HORNSAT peut être résolu en temps polynomial. Il est même PTIME-complet.

HORNSAT ≤ 3HORNSAT ≤ BinOpGen (= Clôture loi binaire) ≤ CIRCUIT-VALUE. Donc 3HORNSAT, BinOpGen et CIRCUIT-VALUE sont PTIME-complets. Prop 16, 19 et 25 du polycopié.

Cf. transparents.

6 (4 jan)

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

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

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

Cf. transparents.

Examens des années précédentes

À propos du LSV