|
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-I-82 at ENS Paris-Saclay each Wednesday,
from 09h30 to 11h30. They are followed by exercise sessions each Friday from 14h00 to 16h00.
Planning: début du cours le 21 sept 2022. Début de la 2ème partie du cours: 16 nov.
Evaluation: Two written exams (see exams from previous years at bottom of page).
The partial exam took place on Nov. 9th, 2022. Here is a version with some answers.
Final exam : Jan. 11th, 2023.
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.
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.)
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.
What we covered in class:
Introduction. Deterministic and nondeterministic Turing machines
Def (2.1) TIME(f), SPACE(f), NTIME, NSPACE, .. P, NP, L, NL, ..
Compression Thm (2.2): 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))
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))
The exercise sheet used on Sept. 23rd is available here.
What we covered in class:
(2.6) GAP is in SPACE(log2(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.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
(2.12) Def. logspace reductions, complete problems & basic properties
GAP is NL-complete
The exercise sheet used on Sept. 30th is available here.
What we covered in class:
What is 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)
SAT is NP-complete (Cook)
QBF is PSPACE-complete
HORNSAT and CIRCUIT-VALUE are P-complete
The exercise sheet used on Oct. 7th is available here.
What we covered in class:
(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 proper f s.t. f(n) ≥ n for large enough n.
This yields e.g. AEXPTIME=EXPSPACE.
(3.18) CIRCUIT_VALUE is PTIME-complete & ALOGSPACE-complete, entailing PTIME=ALOGSPACE, i.e. P=AL,
(3.19) more generally TIME(2^O(f(n)) = ASPACE(f(n)) with f as above, e.g., EXPTIME=APSPACE.
The exercise sheet used on Oct. 14th is available here.
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 first satisfiable 𝜑i has odd index i}, MIN-SAT ≝ {satisfiable Boolean formulae 𝜑(x1,..,xn) such that the lexicography first satisfying valuation vmin has vmin(xn)=true}, etc.
Def (the polynomial hierarchy): PH ≝ all levels Σk with Σ0≝Δ0=Θ0=P(=PTIME) and Σk+1≝NPΣk, Δk+1≝PΣk, Θk+1≝PΣk[O log n], and Πk≝co(Σk).
Facts: Δ1=Θ1=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.
The exercise sheet used on Oct. 21st is available here.
What we covered in class:
Two counting problems #Cycle (≝ count the number of simple cycles in a given graph) and #SAT (≝ count the number of valuations satisfying a given boolean formula).
#SAT is “difficult”, indeed if #SAT ∊ FP then P=NP. Perhaps #Cycle is easier, perhaps in FP (≝ the functions computable in polynomial-time).
Fact: if #Cycle ∊ FP then in that case too P=NP. Proof is by reduction from HamiltonianGraph.
Def. f ∊ #P iff f(x) is the number of accepting paths of a polytime NDTM on x. We can assume that all configurations of the TM have exactly 2 following configurations (or 0) and that all runs have length exactly p(n). Thus #P contains all the functions that counts the “solutions” to NP problems. E.g. #SAT and #Cycle belong to #P.
Obviously if #P = FP then NP = P. We don't know whether the reverse implication holds. However if PSPACE = P then #P = FP.
NB. #P is a class of functions but there are classes of decision problems based on counting accepting runs: PP, ⊕P.
Def. f is #P-complete iff f in #P and g ≤ f for all g in #P. What reductions do we consider? Several versions of parsimonious reductions can be used. Or a more generous g ≤ f iff g in FPf.
Thm. #SAT is #P-complete under parsimonious reductions.
Computing the permanent of a matrix is related to counting the cycle-covers of a directed graph. The definition looks like computing the determinant. However we showed #SAT ≤ PERMANENT ≤ PERMANENT(0/1) so PERMANENT is #P-complete [Valiant 1979]. See wikipedia for a variant proof.
The exercise sheet used on Oct. 26th is available here.
Holidays ! no class this day
The slides of the second part of the course:
The exercise sheets for the second part of the course:
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.
Livres:
Sylvain Périfel. Complexité algorithmique. Ellipses, 2014. Disponible en ligne.
|