M1, 2005–2006

Complexité structurelle – TD 7 Classes probabilistes et de comptage

Exercice 1 Montrer que pour une machine probabiliste M à horloge polynomiale donnée en entrée, les deux problèmes suivants sont indécidables.

1. Sur toute entrée x, soit tous les chemins rejettent, soit la probabilité d’acceptation est ≥ 3/4 (machine RP).

2. Sur toute entrée x, soit la probabilité de rejet est ≥ 3/4, soit la probabilité d’acceptation est ≥ 3/4 (machine BPP).

Exercice 2 Montrer que NP ⊆ PP.

Exercice 3 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 » ?

Exercice 4

1. Montrer que P^{PP} ⊆ P^{#P}.

2. Soit f ∈ #P. Montrer que le langage A = {(x, k)/f(x) ≥ k} est dans PP.

3. En déduire que P^{#P} ⊆ P^{PP}.