Cours de complexité II, ENS Cachan 1ère année

Jean Goubault-Larrecq

LSV/UMR 8643, CNRS, ENS Cachan & INRIA Futurs projet SECSI

61 avenue du président-Wilson, F-94235 Cachan Cedex

goubault@lsv.ens-cachan.fr

Phone: +33-1 47 40 75 68 Fax: +33-1 47 40 75 21

		Cours
Où?	Where?	Bât. Cournot, C205
Quand?	When?	Le vendredi de 14h00 à 16h30
Par qui?	Who?	Jean Goubault-Larrecq (cours)
		Fabrice Chevalier (TD)

Ce cours est la suite du cours de calculabilité et complexité du premier trimestre, par Hubert Comon-Lundh et Jean Goubault-Larrecq.

Il a lieu en alternance avec les TD, un vendredi sur deux. Programme:

10 février 2006, cours 1: la hiérarchie polynomiale, les machines alternantes, la classe PSPACE. QBF est PSPACE-complet.
17 février 2006, cours 2: classes de complexité alternantes, jeux. Les théorèmes de Chandra-Kozen-Stockmeyer: AL=P, AP=PSPACE. HORNSAT est P-complet.
24 février 2006, TD 1.
03 mars 2006, TD 2.
10 mars 2006, cours 3: l'accessibilité dans les graphes orientés est NL-complète. Le théorème d'Immerman-Szelepcsényi: la non-accessibilité dans les graphes orientés est aussi NL-complète. Donc NL=coNL.
17 mars 2006, TD 3.
24 mars 2006, cours 4: classes de complexité randomisées: RP, coRP, BPP, ZPP. Réduction d'erreur. La classe P/poly. Le théorème de Bennett-Gill: BPP ⊆ P/poly. Le théorème de Karp-Lipton; si NP ⊆ BPP alors PH s'effondre au niveau 2. Le théorème de Sipser et Gács: BPP est niveau 2 de la hiérarchie polynomiale.
31 mars 2006, TD 4.
07 avril 2006, cours 5: problèmes d'approximation. Les seuils d'approximation de NODE COVER, TSP, KNAPSACK, MAXSAT. Le théorème d'Arora-Safra: NP=PCP(O (logn), O (1)). Inapproximabilité de MAX3SAT.
28 avril 2006, TD 5.
05 mai 2006, cours 6: Jeux entre Arthur et Merlin. Les classes MA et AM. Le théorème de Babai: MA ⊆ AM, la hiérarchie Arthur-Merlin s'effondre. BP ⋅ NP = AM. Les jeux entre Arthur et Merlin via l'alternance entre quantificateurs E et ∃. Preuves interactives. GRAPH-NON-ISOMORPHISM est dans IP [1]. AM est au niveau 2 de la hiérarchie polynomiale (sans démonstration). Théorème de Goldwasser-Sipser (sans démonstration): IP [k] ⊆ AM [k+1]. Théorème de Boppana-Håstad-Zachos: si coNP ⊆ AM alors PH s'effondre au niveau 2. Conséquence pour GRAPH-NON-ISOMORPHISM.
12 mai 2006, TD 6.
19 mai 2006, cours 7: techniques de hachage universel, GRAPH-NON-ISOMORPHISM est dans AM (preuve directe), l'erreur peut être ramenée à zéro si x in L pour tout langage L de AM, AM est au niveau 2 de la hiérarchie polynomiale (avec démonstration). Classes à nombre de tour polynomial: ABPP, IP. Théorème de Shamir: ABPP=IP=PSPACE.
26 mai 2006: TD 7.

Attention, il risque d'y avoir une réorganisation des dates des TD 6-7 et du cours 7.

Il y a un poly pour tout ce qui est classes randomisées (cours 4-7). La démonstration du théorème d'Arora-Safra y est juste esquissée, et j'ai des doutes quant à sa correction. (Je n'ai plus besoin de l'ingrédient pourtant censément essentiel, de composition des prouveurs.) Je ne fais pas la démonstration du théorème de Goldwasser-Sipser en cours... trop compliqué, je trouve.

Pour les cours précédents, voir le poly de Ralf, accessible depuis la page de son cours de complexité. En particulier, la section 5.2 pour le cours 3, et le chapitre 9 pour les cours 1 et 2.

Examen le vendredi 02 juin, même endroit, mêmes heures. Jusque là, le devoir! A rendre le vendredi 02 juin. Inutile de chercher à le finir lors de l'examen, vous n'aurez pas le temps. C'est l'examen qui comptera pour la note, le devoir comptera essentiellement comme rattrapage... et comme entraînement à l'examen bien sûr.

Quelques sujets d'examens sur des sujets connexes que j'ai posés dans le temps:

(printemps 2005) Complexité de problèmes sur les automates de mots et d'arbres finis, énoncé et corrigé.
(printemps 2006) Mystère!

This document was translated from L^AT_EX by H^EV^EA.

Cours de complexité II, ENS Cachan 1ère année

Jean Goubault-Larrecq LSV/UMR 8643, CNRS, ENS Cachan & INRIA Futurs projet SECSI 61 avenue du président-Wilson, F-94235 Cachan Cedex goubault@lsv.ens-cachan.fr Phone: +33-1 47 40 75 68 Fax: +33-1 47 40 75 21

Jean Goubault-Larrecq

LSV/UMR 8643, CNRS, ENS Cachan & INRIA Futurs projet SECSI

61 avenue du président-Wilson, F-94235 Cachan Cedex

goubault@lsv.ens-cachan.fr

Phone: +33-1 47 40 75 68 Fax: +33-1 47 40 75 21