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 2017-2018

Intervenants: Philippe Schnoebelen puis Jean Goubault-Larrecq pour le cours, et Charlie Jacomme puis Rémy Poulain pour les TDs.

Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle Cournot 419, à l'ENS Cachan. Voir le plan.

Planning: début du cours le 19 sept. 2018. Pas de cours ni TDs le 31 oct. Début de la 2ème partie du cours: 7 nov.

Partial exam : Thursday Oct 24th from 10h45 to 12h45. Here are the answers (thanks to J. Goubault-Larrecq for sharing an earlier version of this problem).

Final exam : TBA

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

Indexes between parentheses are as in the lecture notes (1st part). Exercices sheets and solutions are available on Charlie's webpage.

Sep. 19, 2018

  • Def (2.1) TIME(f(n)), SPACE(f(n)), NTIME, NSPACE, ..
  • Speedup Theorem (2.2)
  • (2.3) REACH aka GAP is in NL aka NSPACE(log(n))

Sep. 26, 2018

  • (2.4) NL ⊆ P
  • (2.6) REACH is in SPACE(log²(n))
  • (2.9) Thm Savitch 1970
  • (2.10) NPSPACE=PSPACE
  • (2.12) Def. logspace reductions & transitivity based on (2.11)

Oct. 3, 2018

  • (2.12) Def. logspace reductions & basic properties. REACH aka GAP is NL-complete for logspace reductions, SAT is NP-complete for logspace reductions.
  • GAP is in coNL
  • (2.17) coNL = NL
  • (2.18) Thm (Immerman-Szelepcsényi 1987) NSPACE(f(n)) = coNSPACE(f(n)) for f≥log

Oct. 10, 2018

  • (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete
  • CIRCUIT_VALUE is PTIME-complete

Oct. 17, 2017

  • HORN-SAT
  • MONOTONIC_CIRCUIT_VALUE ≤_L CIRCUIT_VALUE ≤_L HORN-SAT
  • Alternating Turing machines
  • QBF ∈ AP [aka ATIME(poly(n))] and PSPACE ⊆ AP
  • PSPACE = AP (more generally SPACE(poly(f(n)))=ATIME(poly(f(n))) for f(n)≥n)
  • EXPTIME = APSPACE (more generally TIME(2^{O(f(n))})=ASPACE(f(n)) for f(n)≥n)
  • Between NP and PSPACE: the Polynomial-Time Hierarchy and the Boolean Hierarchy

Langues du cours :

For 2018-2019 the class will be taught in English if at least one non-French-speaking student requires it. 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/)

Polycopiés:

  • première partie et deuxième partie. (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.)

Examens et devoirs

Le corrigé du DM de l'année 2009-2010.

Le corrigé de l'examen de l'année 2009-2010.

Le DM de l'année 2011-2012, et son corrigé.

L'examen de l'année 2011-2012, et son corrigé.

Le DM (avec corrigé) de l'année 2017-2018.

L'examen de l'année 2017-2018, 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