M1, 2005–2006

Complexité structurelle – TD 2 Hiérarchie polynomiale (suite), conseils

1 La 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}.

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

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

Exercice 2

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.

Exercice 3 Soit Minimum circuit le problème suivant : étant donné un circuit booléen en entrée, est-il vrai qu’il n’existe pas de circuit plus petit calculant la même fonction ? Situer Minimum circuit le plus bas possible dans la hiérarchie polynomiale.

2 La classe DP

Définition – Un langage L est dans la classe DP si et seulement s’il existe un langage L_{1} ∈ NP et un langage L_{2} ∈ coNP tels que L = L_{1} ∩ L_{2}. Exercice 4

1. Comparer DP et NP ∩ coNP.

2. Donner un problème DP-complet.

3. Montrer que Unique sat, le problème consistant à déterminer si une formule booléenne est satisfaite par une unique affectation, est dans DP.

3 Classes avec conseil

Exercice 5

1. Montrer que NP ⊂ P/ log ⟺ P = NP.

2. Montrer que

PSPACE ⊂ P/poly ⟹ PSPACE = Σ_{2} ∩ Π_{2}.