M1, 2005–2006

Complexité structurelle – TD 8 Classes de comptage

Exercice 1

1. Montrer que A est dans PP si et seulement s’il existe une machine nondéterministe polynomiale M telle que

x ∈ A ⟺ M(x) a plus de la moitié de chemins acceptant.

2. Soit 0 < α < 1 rationnel. Montrer que A ∈ PP si et seulement s’il existe B ∈ P et un polynôme p(n) tel que

x ∈ A ⟺ |{y ∈ {0, 1}^{p(|x|)}/(x, y) ∈ B}| ≥ α2^{p(|x|)}.

Qu’en est-il si on enlève la contrainte « α rationnel » ?

On rappelle la définition d’un langage p-sélectif A : il existe une fonction f calculable en temps polynomial (f est appelée la fonction de sélection), telle que pour tout x, y ∈ {0, 1}^{∗}, on ait :

– f(x, y) = x ou f(x, y) = y;

– si x ∈ A ou y ∈ A alors f(x, y) ∈ A. Exercice 2

1. Montrer qu’un langage p-sélectif A est dans PP/O(n). On pourra utiliser |A^{=n}| comme conseil.

2. Montrer que dans un tournoi, il existe un sommet duquel tout autre sommet est accessible par un chemin de taille ≤ 2.

3. En déduire qu’un langage p-sélectif est dans NP/(n + 1). Remarque : on sait construire un langage p-sélectif qui n’est pas dans NP/n.

Exercice 3 FewP est l’ensemble des langages reconnus par machines non-déterministes polynomiales, ayant au plus un nombre polynomial de chemins acceptant. Montrer que FewP ⊆ ⊕P.

Exercice 4 (Question ouverte) Donner une fonction f ∈ #P telle que P^{f} = P^{NP}. On pourra se contenter de P^{NP} ⊆ P^{f} ⊆ PH. Ou alors, montrer qu’un tel f n’existe pas.