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 2019-2020

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

The lectures take place online each Wednesday, from 8h30 to 10h30. They are followed by exercise sessions, also online, from 10h45 to 12h45. Beware that the two online links are different.

Planning: début du cours le 23 sept 2020. Pas de cours ni TDs le 28 oct ni le 11 nov. Début de la 2ème partie du cours: 18 nov.

Évaluation: la note globale combine à part égale une note pour chacune des deux parties du cours. Pour la 1ère partie, la note sera constituée de la note du partiel améliorée par la note des DM hebdomadaires donnés en TD.

Partial exam: To account for the recent sanitary restrictions, the partial exam took the form of a homework issued on Nov 4th and to be returned no later than Nov. 18th, 12AM. Answers are now available here.

Final exam, as a homework assignment, again due to sanitary restrictions. Please turn it in to Jean Goubault-Larrecq on or before Friday, January 22nd, 2021. The use of LaTeX is encouraged. Otherwise, please write readably and send a scan of good quality. Here is a possible solution.

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.)

This page will be updated after each class with a summary of what has been covered (for the first part only). Numbers, e.g. ”(2.1)”, refer to statement in the lecture notes.

Sep. 23, 2020

  • Def (2.1) TIME(f), SPACE(f), NTIME, NSPACE, ..
  • Speedup & Compression Theorems (2.2), including ∀ε>0 : TIME(f) ⊆ TIME(εf+n+2)
  • Lem (2.3) GAP aka REACH is in NL aka NSPACE(log(n))

Sep. 30, 2020

  • GAP is in SPACE(log2(n))
  • A TM in space f(n) running on input x has at most ≈ |Q| × f(n)^{log |Σ|} × [log f(n)]^k x n configurations, i.e. O(n x f(n)^{1+log |Σ|}).
  • (2.4) NL ⊆ P
  • (2.9) Thm (Savitch 1970) NSPACE(f(n)) ⊆ SPACE(f²(n)) when f is constructible, increasing & ≥log.
  • (2.16) Thm (Immerman-Szelepcsényi 1987) coGAP is in NL.
  • (2.17) Hence NL=coNL.

Oct. 6, 2020

  • (2.12) Def. logspace reductions, complete problems & basic properties.
  • REACH aka GAP is NL-complete.
  • SAT is NP-complete.
  • QBF is PSPACE-complete (we only had time to prove that QBF ∈ PSPACE).

Oct. 14, 2020

  • (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 f constructible and 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. 21, 2020

  • 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.
  • Some complete problems: ∃**SAT is Σ2-complete, in fact ∃****.. (∃*/∀*)nSAT is Σn-complete; SAT-UNSAT and UNIQ-SAT are DP-complete, where DP=NP⋀coNP; PARITY-SAT is Θ2-complete; MIN-SAT is Δ2-complete.

* Here are: the Exercise sheet 5; its correction; the Homework exercise 5; its correction.

Starting Nov. 18, 2020: 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.

Examens et devoirs

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

 
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