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 2022-2023

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

For the first half (until partial exam on November 9th) the lectures take place in room 1-E-14 at ENS Paris-Saclay (Bât. Sud-Ouest), each Monday, from 08h30 to 10h30, followed by exercise sessions from 10h45 to 12h45.

Planning: début du cours le 18 sept 2023. Début de la 2ème partie du cours: 13 nov 2023.

Evaluation: Two written exams (see exams from previous years at bottom of page).

Partial exam : Nov. 6th, 2023 from 08h30 to 10h00. See the exam questions and some sketch answers.

Final exam : Monday, Jan. 15th 2024, same room (1E14), ENS Paris-Saclay, 9h30-12h30. All written documents allowed (I recommend printing selected excerpts from the lecture notes). No Internet access, no cell phone. You can answer in French or in English. Here is the exam, and 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.)

Starting Sep. 18, 2023: 1st part of the course

After each class, this section will be updated with a summary of the material actually covered. Numbers, e.g. ”(2.1)”, refer to statement in the lecture notes.

Sep. 18, 2023

What we covered in class:

  • Introduction. Deterministic and nondeterministic Turing machines
  • Def (2.1) TIME(f), SPACE(f), NTIME(f), NSPACE(f), .. P, NP, L, NL, ..
  • GAP (aka REACH), a problem on directed graphs
  • How do we see it as a language GAP⊆Σ*?
  • (2.3) GAP is in NL, i.e. NSPACE(log(n))

Corresponding exercise sheet : TD1

Sep. 25, 2023

What we covered in class:

  • (2.2) Compression Thm: SPACE(O(f(n))) ⊆ SPACE(f(n)) and NSPACE(O(f(n))) ⊆ NSPACE(f(n))
  • For proper function f, NTIME(f(n)) ⊆ SPACE(f(n)) and NSPACE(f(n)) ⊆ TIME(2(f(n)+log 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.6) GAP is in SPACE(log2(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 proper & ≥log
  • (2.10) Hence NPSPACE=NSPACE(nO(1))=SPACE(nO(1))=PSPACE

Corresponding exercise sheet : TD2

Oct. 2, 2023

What we covered in class:

  • (2.12) Def. logspace reductions
  • (2.11) Logspace reducibility, L ≤ L' is reflexive and transitive
  • L, NL, P, NP, ..., are closed under reducibility
  • Def. 𝒞-complete problems for a class 𝒞
  • (2.13) Thm. GAP is NL-complete
  • (2.14) Thm (Cook 1971). SAT is NP-complete

Corresponding exercise sheet : TD3

Oct. 9, 2023

What we covered in class:

  • Def. co𝒞 and coL for 𝒞 a class of problems (or languages) and L a problem.
  • (2.16) coGAP is in NL, hence (2.17) coNL = NL (Immerman-Szelepcsényi)
  • (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.
  • HornSAT is in P

Corresponding exercise sheet : TD4

Oct. 16, 2022

What we covered in class:

  • Circuits and their evaluation. CIRCUIT-VALUE[∧,∨,¬,⊥,⊤], CIRCUIT-VALUE[NAND] and CIRCUIT-VALUE[∧,∨] are logspace-equivalent (i.e., inter-reducible).
  • (3.10) CIRCUIT-VALUE ≤ HORNSAT.
  • (3.18) CIRCUIT_VALUE is PTIME-complete & ALOGSPACE-complete, entailing PTIME=ALOGSPACE, i.e. P=AL, and showing that HORNSAT too is P-complete and AL-complete.

What we did not have time to see but should read in the lecture notes:

  • (3.8) Padding lemma.
  • (3.9 & 3.19) This yields e.g. AEXPTIME=EXPSPACE from AP = PSPACE and EXPTIME=APSPACE from P=AL.

Corresponding exercise sheet : TD5

Oct. 23, 2023

What we covered in class:

  • TM machines that access an oracle O (can be any language ⊆A*). In a run of MO, there is a special query tape where the TM might write a query q. When M enters the querying state, q is erased and the TM jumps to state syes or sno depending on whether q∊O. When measuring space usage, the query tape in counted.
  • Def: (given a language O) ℳO for a class ℳ of machines, e.g. PO, NPO, etc., similarly P𝒞, NP𝒞, etc. for a class 𝒞 of oracles.
  • Some problems in PSAT: UNSAT, SAT-UNSAT, UNIQ-SAT (Boolean formulae with only one satisying valuation), PARITY-SAT ≝ {(𝜑1,...,𝜑n) such that the number of satisfiable 𝜑i's is odd}, MAX-SAT ≝ {satisfiable Boolean formulae 𝜑(x1,..,xn) such that the lexicography largest satisfying valuation vmin (exists and) has vmin(xn)=true}, etc.
  • Def (the polynomial hierarchy): PH ≝ all levels Σk with Σ0≝Δ00=P(=PTIME) and Σk+1≝NPΣk, Δk+1≝PΣk, Θk+1≝PΣk[O log n], and Πk≝co(Σk).
  • Facts: Δ11=P and Σ1=NP. Also Πk=(coNP)Σk where coNP seen as a class of machines comprises all polynomial-time TMs with only universal states.
  • Thm: (Σk-1 ∪ Πk-1) ⊆ Θk ⊆ Δk ⊆ (Σk ∩ Πk).
  • Thm: Σk ⊆ PSPACEPSPACE = PSPACE for all k, hence PH ⊆ PSPACE.
  • Thm: If PH=PSPACE then PH has a complete problem. If PH has a complete problem then PH coincides with some Σn level (we say “PH collapses”).
  • Some complete problems for specific levels in PH: the ∃** fragment of QBF is Σ2-complete, in fact the ∃****.. (∃*/∀*)k fragment is Σk-complete; PARITY-SAT is Θ2-complete; MIN-SAT and UNIQ-TSP (graphs with a unique Hamiltonian circuit of minimal length) are Δ2-complete.
  • Thm: Θk+1 = PΣk, where polynomially many queries can be submitted to the oracle, but they have to be computed in advance so that they can all be answered “in parallel”, in just one round.
  • Def (the Boolean hierarchy): BH ≝ all levels BHk with BH1≝NP, BH2k≝BH2k-1⋀coNP, and BH2k+1≝BH2k⋁NP. DP is another name for BH2, i.e. NP⋀coNP. Recall that 𝒞⋀𝒞' is defined as {L∩L'|L∊𝒞 and L'∊𝒞'}, so that one has 𝒞∩𝒞' ⊆ 𝒞,𝒞' ⊆ 𝒞⋀𝒞' (NB: the last inclusion assumes that 𝒞 and 𝒞' contain the universal languages A* for any alphabet). There is a similar definition for 𝒞⋁𝒞.
  • SAT-UNSAT and UNIQ-SAT are DP-complete, where DP=NP⋀coNP. There exist complete problems for each level of BH. If BH itself has a complete problem, then it collapses to some level BHk.
  • Facts: BH = PNP[O(1)] hence BH ⊆ Θ2. If BH=Θ2 then BH collapses.

Corresponding exercise sheet : TD6

Starting Nov. 13, 2023: 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

Students are expected to be familiar with the concepts and formal definitions for Turing Machines, the class P (problems decidable in deterministic polynomial time), the class NP (non-deterministic polynomial-time), Cook's Theorem (SAT is NP-complete). These notions will only be very quickly recalled during the first classes.

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 final 2021-22, en temps limité. Voici un corrigé.

Le partiel 2022-23, en temps limité. Voici un corrigé.

L'examen final 2022-23, en temps limité. Voici un corrigé.

Le partiel 2023-24, 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