Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

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

Plan et intervenants du cours 2009-2010 :

Les cours auront lieu le Mercredi de 8h45 à 11hh45 rue du Château des Rentiers
Par défaut on fait 90mn de cours puis 90mn de TD

Début du cours le Mercredi 16 Septembre.
Fin du cours le Mercredi 27 Janvier

Partiel prévu le 18 Novembre durant l'heure habituelle du cours

Exam prévu le 10 Février durant l'heure habituelle du cours

Motivations et objectifs du cours

La théorie de la complexité va bien au-delà de celle des classes P et NP. L'objectif de ce cours est d'étudier la complexité en mémoire et la notion de machine de Turing alternantes. On étudiera des classes de complexités plus petites que P. Pour cela on introduira d'autres notions que la réduction polynomiale.

On introduira aussi la notion de complexité paramétrée qui raffine la notion de complexité.

Description du cours

• La complexité en fonction du temps. Machine de Turing. Déterminisme et non déterminisme. Calculabilité et problème de l'arrêt. Machine de Turing Universelle. Définition des classes P, NP, ExpTime et NExpTime. Théorème de hiérarchie et diagonalisation. Si P=NP alors ExpTime=NExpTime. Réductions polynomiales et complétude. Exemples de problème NP-complets, ExpTime-complet, NExpTime-complet. Théorème de Ladner.

• La complexité en mémoire. Les classes L, NL, PSpace et ExpSpace. Théorème de hiérarchie et diagonalisation. Les liens entre l'espace et le temps. Le théorème de Savitch et celui d'Immerman-Szlepcsenyi. Les réductions L. NL-complétude de REACH. PTime complétude.

• Hiérarchie polynomiale, machines de Turing alternantes et les liens avec les notions précédentes.

• Circuit complexity I: P/poly, uniformité LogSpace, hiérarchie NC et AC, comparaison avec NL et PTime.

• Circuit Complexity II: LogCFL=SAC1, LogCFL-complétude et clôture par complément de LogCFL.

• Circuit complexity III: NC1, AC0, réductions FO. Langages réguliers et NC1-complétude. Accessibilité dans les arbres est L-complet.

• Complexité Paramétrée: notions de bases et applications.

Langues du cours :

Le cours sera a priori en français.
Cependant, s'il est suivi par des étudiants non francophones et en accord avec l'ensemble des étudiants qui le suivent, ce cours pourra aussi être en anglais.

Le sujet d'examen sera en anglais.
Les étudiants seront autorisés à rédiger leur 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

Complexité et Calculabilité

Bibliographie

Livres:

• Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer 2006.
• Heribert Vollmer. Introduction to Circuit Complexity - A Uniform approach. EATCS series. Springer Verlag, 1999.
• 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:

• Jean Goubault-Larrecq:le poly de son cours de l'an dernier
• Ralf Treinen: Notes de cours

Examens et devoirs

Les feuilles de TDs peuvent être récupérées ici.

Les années précédentes

• Année 2009-2010
• Année 2008-2009
• Année 2007-2008
• Année 2006-2007^?

Équipe pédagogique

Luc Segoufin