Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Complexité avancée (48h, 6 ECTS)

Responsable : Jean Goubault-Larrecq (LSV, ENS Cachan).

Plan et intervenants du cours 2021-2022

Lecturers: Philippe Schnoebelen then Jean Goubault-Larrecq for the course, and Benjamin Bordais for the exercise sessions (TD).

The lectures take place at ENS Paris-Saclay room 1Z53 (see map) each Wednesday, from 8h30 to 10h30. They are followed by exercise sessions from 10h45 to 12h45.

Planning: début du cours le 22 sept 2021. Début de la 2ème partie du cours: 17 nov.

Evaluation: Two written exams (see exams from previous years at bottom of page). Bonus points will be awarded for quality work done during exercise sessions.

Partial exam : Nov. 10th, 2021 at 09h45 AM in room 1Z53. Duration = 2 hours. No class this day.

Final exam : Jan. 12th, 2022, 8h30-10h30 am, room 1Z53. Of course no exercise session after that.

Motivations et objectifs du cours

La théorie de la complexité va bien au-delà de celle de la NP-complétude. Le but de ce cours est d'aller regarder un certain nombre d'autres constructions fondamentales de la théorie de la complexité: complexité en espace, notions de machines alternantes, ou randomisées. On y verra quelques théorèmes fascinants: l'équivalence du temps alternant et de l'espace déterministe par exemple, ou le théorème IP=PSPACE de Shamir.

Description du cours

The course is based on the following lecture notes polycopié (1st part) and polycopié (2nd part). (Note: il semble que le premier poly ait des problèmes de polices sous Acrobat Reader 9; aucun problème connu sous xpdf ou evince.)

Starting Sep. 22, 2021: 1st part of the course

This page will be updated after each class.

Numbers, e.g. ”(2.1)”, refer to statement in the lecture notes.

Sep. 22, 2021

  • Introduction. Deterministic and nondeterministic Turing machines
  • Def (2.1) TIME(f), SPACE(f), NTIME, NSPACE, .. P, NP, L, NL, ..
  • Compression Thm (2.2): SPACE(O(f(n))) ⊆ SPACE(f(n))
  • Speedup Thm: for f constructible ∀ε>0 : TIME(f) ⊆ TIME(εf+n+2)

Sep. 29, 2021

  • GAP (aka REACH), a problem on directed graphs
  • How do we see it as a language GAP⊆Σ*?
  • (2.3) GAP is in NL aka NSPACE(log(n))
  • (2.6) GAP is in SPACE(log2(n))
  • A k-worktape (N)TM in space f(n) running on input x visits at most ≈ |Q| × |Σ|f(n) x n × f(n)k different configurations, i.e. O(n) x 2O(f(n))
  • (2.4) NL ⊆ P (aka PTIME) and NL ⊆ SPACE(log2n)
  • (2.9) Thm (Savitch 1970) NSPACE(f(n)) ⊆ SPACE(f²(n)) when f is constructible, increasing & ≥log
  • (2.10) Hence NPSPACE=PSPACE

Oct. 6, 2021

  • (2.12) Def. logspace reductions, complete problems & basic properties
  • GAP is NL-complete
  • SAT is NP-complete
  • HORNSAT is P-complete
  • QBF is PSPACE-complete

Oct. 13, 2021

  • (3.1;3.2) Alternating Turing machines. The classes ATIME(f) & ASPACE(f) are closed under complementation.
  • (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete and APTIME-complete, hence PSPACE=APTIME.
  • (3.8) Padding lemma, entailing (3.9) SPACE(poly(f(n)) = ATIME(poly(f(n)) for any proper f s.t. f(n) ≥ n for large enough n.
  • (3.18) CIRCUIT_VALUE is PTIME-complete & ALOGSPACE-complete, entailing PTIME=ALOGSPACE, i.e. P=AL, and more generally (3.19) TIME(2^O(f(n)) = ASPACE(f(n)) with f as above.

Oct. 20, 2021

  • TM machines that access an oracle O.
  • Def: PO, NPO, etc., for a language O⊆A*, similarly P𝒞, etc. for a class 𝒞.
  • Solving problems within PSAT: UNSAT, SAT-UNSAT, UNIQ-SAT, PARITY-SAT, MIN-SAT, etc.
  • Def: PH = all levels Σk with Σ000=P(=PTIME) and Σk+1=NPΣk, Δk+1=PΣk, Θk+1=PΣk=PΣk[O log n], and Πk=co-Σk.
  • Facts: Δ11=P and Σ1=NP.
  • Thm: (Σk-1 ∪ Πk-1) ⊆ Θk ⊆ Δk ⊆ (Σk ∩ Πk).
  • Thm: PH ⊆ PSPACE. If PH=PSPACE then PSPACE and PH coincide with some Σn level. If PH has a complete problem then again PH is some Σn.
  • Some complete problems: ∃**SAT is Σ2-complete, in fact ∃****.. (∃*/∀*)nSAT is Σn-complete; PARITY-SAT is Θ2-complete; MIN-SAT and UNIQ-TSP are Δ2-complete; SAT-UNSAT and UNIQ-SAT are DP-complete, where DP=NP⋀coNP. Recall that 𝒞⋀𝒞' is defined as {L∩L'|L∊𝒞 and L'∊𝒞'}, so that one has 𝒞∩𝒞' ⊆ 𝒞,𝒞' ⊆ 𝒞⋀𝒞'.
  • DP is another name for BH1, the first level of the Boolean Hierarchy, given by BH0=NP, BH2n+1=BH2n⋀coNP and BH2n+2=BH2n+1⋁NP. Note that BH=⋃k∊ℕBHk is included in Θ2.

Oct. 27, 2021

  • #P, a complexity class for functions that count: #SAT is #P-complete.
  • Computing the permanent is hard: #SAT ≤ PERMANENT ≤ PERMANENT(0/1) so PERMANENT is #P-complete [Valiant 1979].
  • Undecidable problems and the arithmetical hierarchy.

Nov. 3rd, 2021

Holidays ! no class this day

Starting Nov. 17, 2021: 2nd part of the course

The slides of the second part of the course:

Langues du cours :

The class will be taught in English. Le polycopié est en français et les élèves peuvent poser des questions, intervenir, etc. en français.

Les questions des sujets d'examen seront en anglais. Les étudiants seront autorisés à rédiger leur copie d'examen en français ou en anglais.

Pré-requis

On s'attend à ce que les étudiants aient une certaine familiarité avec la notion de Machine de Turing, la classe P (temps polynomial déterministe), la classe NP (temps polynomial non-déterministe), les notions de réductions en temps polynomial, le théorème de Cook (SAT est NP-complet) même si toutes ses notions seront rapidement revues au début du cours.

Cours liés

Bibliographie

Livres:

  • Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  • Sanjeev Arora and Boaz Barak. Computational Complexity. Cambridge University Press, 2009.
    (une pré-version est gracieusement disponible ici http://www.cs.princeton.edu/theory/complexity/)
  • Sylvain Périfel. Complexité algorithmique. Ellipses, 2014. Disponible en ligne.

Archive: examens et devoirs des années précédentes

L'examen de l'année 2017-2018, et son corrigé.

Le partiel (corrigé) de l'année 2018-2019.

Le partiel (corrigé) de l'année 2019-2020.

L'examen de l'année 2019-2020, et son corrigé.

L'examen partiel de l'année 2020-2021 a pris la forme d'un DM à cause des mesures sanitaires. Voici un corrigé.

L'examen final de l'année 2020-2021 a pris lui aussi la forme d'un DM. Voici un corrigé.

L'examen final 2021-22, en temps limité. Voici un corrigé.

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA