M1, 2005–2006

Complexité structurelle – TD 1 Oracles et hiérarchie polynomiale

On rappelle la définition de la hiérarchie polynomiale :

Σ_{0} = Π_{0} = Δ_{0} = P,

et pour k ≥ 1,

Σ_{k} = NP^{Σ_{k−1}}, Π_{k} = coNP^{Σ_{k−1}}, Δ_{k} = P^{Σ_{k−1}}.

Enfin,

PH = ∪_{k}Σ_{k}.

1 Oracles

Exercice 1

1. Se remémorer la définition d’une classe avec oracle. Expliquer pourquoi deux classes de complexité peuvent être égales, et pourtant différentes relativement à un oracle (par exemple, IP et PSPACE). Et inversement.

2. Si C, C_{1} et C_{2} sont trois classes de complexité, a-t-on C_{1} = C_{2} ⟹ C^{C_{1}} = C^{C_{2}} ?

3. Voir pourquoi il se pourrait que P^{NP} ≠ NP.

Exercice 2 Montrer qu’il existe un oracle A tel que P^{A} = NP^{A}, et un oracle B tel que P^{B} ≠ NP^{B}. Utiliser la question 1 de l’exercice 1 pour voir que cela n’implique pas trivialement P ≠ NP.

2 La hiérarchie polynomiale

Exercice 3

1. Montrer que Π_{k} = coΣ_{k}.

2. Montrer que A ∈ Σ_{k} si et seulement s’il existe B ∈ P et un polynôme p(n) tels que

x ∈ A ⟺ ∃y_{1} ∈ {0, 1}^{p(|x|)} ∀y_{2} ∈ {0, 1}^{p(|x|)} … Q y_{k} ∈ {0, 1}^{p(|x|)} (x, y_{1} … y_{k}) ∈ B,

et de même pour Π_{k} en commençant par ∀.

3. Montrer que si Σ_{k} = Π_{k} pour un certain k ≥ 1, alors PH = Σ_{k}.

Exercice 4 Montrer que PH ⊆ PSPACE. Récapitulons les inclusions connues :

[figure: P; Σ_{0} Π_{0}; Δ_{0} Δ_{1}; Σ_{1}; Π_{1}; Δ_{2}; Σ_{2}; Π_{2}; Δ_{3}; ⋯; PSPACE]

Exercice 5

1. Donner un problème complet SAT_{k} pour chaque Σ_{k}, k ≥ 1.

2. Montrer que si PH admet un problème complet, alors pour un certain k, PH = Σ_{k}.

3. Montrer que PSPACE = PH implique PSPACE = PH = Σ_{k} pour un certain k.