RP (complexité)

En informatique théorique, plus précisément en théorie de la complexité, la classe RP (Randomized Polynomial time) est la classe de complexité des problèmes de décision pour lesquels il existe une machine de Turing probabiliste, en temps polynomial, qui refuse toutes les instances négatives et accepte les instances positives avec une probabilité supérieure à 1/2.

Exemple

Définition

Une première définition

La classe RP est l'ensemble des problèmes, ou de façon équivalente des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes :

Si le mot n'est pas dans le langage, la machine le rejette.
Si le mot est dans le langage, la machine l'accepte avec une probabilité supérieure à 1/2.

On dit que la machine « ne se trompe que d'un côté »^{[réf. nécessaire]}.

Définition formelle

Pour un polynôme $T$ en la taille de l'entrée $n$ , on définit $RTIME(T(n))$ , l'ensemble des langages $L$ pour lesquels il existe une machine de Turing probabiliste $M_{L}$ , en temps $T(n)$ , telle que pour tout mot $x$ :

$x\notin L\Rightarrow Pr(M_{L}(x)=0)=1$ .
$x\in L\Rightarrow Pr(M_{L}(x)=1)\geq {\frac {1}{2}}$ .

Alors on peut définir RP comme : $RP=\cup _{p\in N}RTIME(n^{p})$ .

Le rôle de la constante

La constante 1/2 est en fait arbitraire, on peut choisir n'importe quel nombre (constant) entre 0 et 1 (exclus)^[1].

L'idée est qu'en faisant le calcul indépendamment un nombre polynomial de fois $p(n)$ , on peut faire chuter la probabilité d'erreur à $\left({\frac {1}{2}}\right)^{p(n)}$ dans le cas $x\in L$ (tout en gardant une réponse sûre dans le cas $x\not \in L$ ).

La classe co-RP

La classe co-RP est l'ensemble des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes :

Si le mot est dans le langage, la machine l'accepte.
Si le mot n'est pas dans le langage, la machine le rejette avec une probabilité supérieure à 1/2.

(Même remarque sur la constante)

Relations avec les autres classes

Avec les classes "classiques"

On a la relation suivante avec les classes P et NP : $P\subseteq RP\subseteq NP$

Démonstration

On utilise la définition de machine de Turing probabiliste avec bande d'aléa.

$P\subseteq RP$ : il suffit de faire le calcul de la machine de P (en ignorant la bande d'aléa), la probabilité d'erreur est alors nulle dans les deux cas (appartenance ou pas).

$RP\subseteq NP$ : Soit M une machine en temps polynomial randomisé qui décide $L\in RP$ . On construit une machine M' de NP qui devine une bande d'aléa telle que M accepte. Si la bande devinée fait vraiment accepter M, alors M' accepte sinon elle rejette.

S'il existe une "bonne" bande, comme M ne se trompe pas, c'est que le mot considéré est dans $L$ . Réciproquement si le mot est dans $L$ , M accepte avec une probabilité au moins 1/2, i.e. M accepte sur la moitié des bandes d'aléa, donc il existe au moins une bande d'aléas faisant accepter et donc M' la devine et accepte.

Remarquons que cette classe n'est plus intéressante si P=NP.

Valiant et Vazirani ont démontré^[2] que $NP\subseteq RP^{USAT}$ où USAT est le problème SAT, où on promet que la formule booléenne en entrée admet au plus qu'une solution. L'oracle à USAT fonctionne comme suit : il répond positivement sur des formules qui ont exactement une unique solution, il répond négativement sur des formules sans solution, et il répond de manière arbitraire sur les autres formules.

Avec les autres classes probabilistes

Les inclusions suivantes mettent en jeu les classes ZPP et BPP.

$ZPP\subseteq RP\subseteq BPP$

Cela vient directement des définitions : ZPP est l'intersection de RP et co-RP et BPP a des conditions d'acceptation moins contraignantes (erreur « des deux côtés »).

Problèmes dans RP et co-RP

Les problèmes de RP sont des problèmes pour lesquels il existe un algorithme probabiliste qui satisfait les conditions décrites plus haut.

Par exemple le problème de savoir si un entier est premier est dans co-RP grâce au test de primalité de Miller-Rabin. En fait, ce problème est même dans P, grâce au test de primalité AKS.

Un problème de co-RP qui n'est pas connu comme étant dans P est le problème polynomial identity testing, qui consiste, étant donné un polynôme multivarié sous une forme quelconque, à décider s'il est identiquement nul ou non. Grâce au lemme de Schwartz-Zippel, on peut reconnaître les polynômes nuls avec une bonne probabilité en les évaluant en un petit nombre de points.

Histoire

Cette classe a été introduite par J. Gill^[3] dans l'article Computational complexity of probabilistic Turing machines (Gill 1977).

Bibliographie

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7
(en) John Gill, « Computational complexity of probabilistic Turing machines », SIAM Journal on Computing, vol. 6, n^o 4,‎ 1977, p. 675-695

Lien externe

(en) La classe RP sur le Complexity Zoo

Notes et références

↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7
↑ L. G. Valiant et V. V. Vazirani, « NP is as easy as detecting unique solutions », Theoretical Computer Science, vol. 47,‎ 1^er janvier 1986, p. 85–93 (ISSN 0304-3975, DOI 10.1016/0304-3975(86)90135-0, lire en ligne, consulté le 11 juillet 2019)
↑ Complexity Zoo

Portail de l'informatique théorique

[1] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7

[2] L. G. Valiant et V. V. Vazirani, « NP is as easy as detecting unique solutions », Theoretical Computer Science, vol. 47,‎ 1^er janvier 1986, p. 85–93 (ISSN 0304-3975, DOI 10.1016/0304-3975(86)90135-0, lire en ligne, consulté le 11 juillet 2019)

[3] Complexity Zoo

[1]

[2]

[3]