M1, 2005–2006

Complexité structurelle – TD 6 Classes probabilistes, 2

Si on ordonne les mots sur {0, 1} par ordre lexicographique, on peut parler du i-ème mot binaire, que l’on notera x_{i}. À un langage L on associe la suite u ∈ {0, 1}^{N} définie par

u_{i} = \{ \begin{matrix}1 & si x_{i} ∈ L \\ 0 & sinon. \end{matrix}

Enfin, sur l’ensemble des suites de {0, 1}, on met la mesure de probabilité uniforme : elle est induite par la mesure d’équiprobabilité sur {0, 1}, ou en d’autres termes, pour tout i, la probabilité que u_{i} = 1 est 1/2. On peut ainsi parler d’oracle aléatoire. Exercice 1 On veut montrer que P^{A} = BPP^{A} avec probabilité 1, c’est-à-dire que pour presque tout oracle A, P^{A} = BPP^{A}.

1. D’abord, quelques définitions. Le but du jeu est donc de montrer que pour tout δ > 0, la probabilité que P^{A} ≠ BPP^{A} est < δ. On considère pour cela une énumération (M_{i}) des machines de Turing probabilistes fonctionnant en temps polynomial. On dira que la machine M_{i} est de type BPP avec l’oracle A si pour tout x, dans le calcul de M_{i}^{A} sur x, soit la proportion de chemins acceptant est d’au moins 3/4, soit la proportion de chemins rejetant est d’au moins 3/4. On notera p_{i}(n) le temps de calcul de la machine M_{i} sur des entrées de taille n.

2. L’idée est d’utiliser l’oracle A comme source de bits pseudo-aléatoires. Pour obtenir des bits « aléatoires », on interrogera A sur des mots que la machine M_{i} ne demandera pas. Par ailleurs, avec ces bits on souhaite simuler M_{i} plusieurs fois de façon à réduire suffisamment la probabilité d’erreur. Proposer une machine déterministe D_{i} avec oracle, fonctionnant en temps polynomial, qui calcule des bits pseudo-aléatoires grâce à son oracle, et qui s’en sert pour simuler M_{i} (avec le même oracle) un nombre de fois k à déterminer plus tard.

3. Si i est un entier et x un mot binaire, on note E_{i,x} l’ensemble

E_{i,x} = {A; M_{i} avec oracle A est de type BPP, et D_{i}^{A}(x) ≠ M_{i}^{A}(x)}.

Majorer Prob(A ∈ E_{i,x}) en fonction du nombre k de simulations de M_{i} dans la question précédente.

4. Supposons que P^{A} ≠ BPP^{A} pour un certain ensemble A. A est-il dans un des E_{i,x} avec |x| > i?

5. Majorer la probabilité que P^{A} ≠ BPP^{A} en fonction de k, choisir k correctement et conclure.

Un circuit arithmétique est un circuit (graphe orienté sans cycle) ayant pour entrées des indéterminées x_{i} et la constante 1, et ayant pour portes +, − et ×.

Ainsi, un tel circuit calcule un polynôme dans Z[x_{1}, …, x_{k}]. La taille du circuit est le nombre de sommets du graphe.

Soit Polynôme nul le problème suivant. En entrée, on donne un circuit arithmétique C. Il calcule un polynôme f(x_{1}, …, x_{k}) ∈ Z[x_{1}, …, x_{k}]. Il s’agit de décider si f = 0. Exercice 2

1. Majorer la valeur absolue des nombres que l’on peut calculer avec un tel circuit en fonction de sa taille et du max de la valeur absolue des x_{i}.

2. Proposer un algorithme coRP pour Polynôme nul.

3. Soit le problème suivant, où C_{1} et C_{2} sont des circuits arithmétiques :

{(C_{1}, C_{2}) : C_{1} ∈ Polynôme nul et C_{2} ∉ Polynôme nul}.

Donnez la plus petite classe de complexité dans laquelle vous pouvez mettre ce problème.

On ne sait pas si RP est clos par complément, ou en d’autres termes si RP = coRP. Ainsi, on définit la classe ZPP (zero error probabilistic polynomial time) par ZPP = RP ∩ coRP. Exercice 3 Montrer qu’un langage A est dans ZPP si et seulement s’il existe pour A un algorithme probabiliste dont le temps d’exécution dans le pire cas est polynomial, qui a la possibilité de répondre « je ne sais pas » mais avec probabilité < 1/3, et qui ne se trompe jamais dans les autres cas. (Algorithmes de Las Vegas)

Montrer une autre caractérisation : A est dans ZPP si et seulement s’il existe pour A un algorithme probabiliste ne se trompant jamais, et dont le temps moyen d’exécution est polynomial.

Exercice 4 Montrer que si NP ⊆ BPP alors NP ⊆ RP.

Exercice 5 Reprendre les exercices 2 et 3 du TD5 avec BPP à la place de RP.