Voir la source de RP (complexité)

[[Fichier:Randomized Complexity Classes.svg|thumb|Inclusions de classes de complexité probabilistes.]]En [[informatique théorique]], plus précisément en [[théorie de la complexité (informatique théorique)|théorie de la complexité]], la '''classe RP''' (''Randomized Polynomial time'') est la [[classe de complexité]] des [[problème de décision|problèmes de décision]] pour lesquels il existe une [[machine de Turing probabiliste]], en temps [[polynôme|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 [[langage formel|langages]], pour lesquels il existe une [[machine de Turing probabiliste]] en temps [[polynôme|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érence nécessaire|date=15 octobre 2017}}.

===Définition formelle===
Pour un polynôme <math>T</math> en la taille de l'entrée <math>n</math>, on définit <math>RTIME(T(n))</math>, l'ensemble des langages <math>L</math> pour lesquels il existe une [[machine de Turing probabiliste]] <math>M_L</math>, en temps <math>T(n)</math>, telle que pour tout mot <math>x</math> : 
* <math>x \notin L \Rightarrow Pr(M_L(x)=0)=1 </math> .
* <math>x \in L \Rightarrow Pr(M_L(x)=1)\geq \frac{1}{2}</math>.

Alors on peut définir '''RP''' comme : <math>RP=\cup_{p\in \mathbb{N}} RTIME(n^p)</math>.

===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)<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=7}}</ref>. 

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

==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 (complexité)|P]]''' et '''[[NP (complexité)|NP]]''' : <math>P \subseteq RP \subseteq NP</math>

{{démonstration 
|  contenu=
On utilise la définition de [[machine de Turing probabiliste]] avec bande d'aléa.

<math>P\subseteq RP</math> : 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).

<math> RP \subseteq NP</math> : Soit M une machine en temps polynomial randomisé qui décide <math>L \in RP</math>. 
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 <math>L</math>.  
Réciproquement si le mot est dans <math>L</math>, 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 '''[[Problème P = NP|P=NP]]'''.

Valiant et Vazirani ont démontré<ref>{{Article |prénom1=L. G. |nom1=Valiant |prénom2=V. V. |nom2=Vazirani |titre=NP is as easy as detecting unique solutions |périodique=Theoretical Computer Science |volume=47 |date=1986-01-01 |issn=0304-3975 |doi=10.1016/0304-3975(86)90135-0 |lire en ligne=http://www.sciencedirect.com/science/article/pii/0304397586901350 |consulté le=2019-07-11 |pages=85–93 }}</ref> que <math>NP \subseteq RP^{USAT}</math>où USAT est le problème SAT, où on promet que la formule booléenne en entrée admet au plus une solution. L'[[Oracle (machine de Turing)|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 (complexité) |ZPP]]''' et '''[[BPP (complexité)|BPP]]'''.

<math> ZPP \subseteq RP \subseteq BPP</math>

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<ref>[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R Complexity Zoo]</ref> dans l'article ''Computational complexity of probabilistic Turing machines'' {{harv|Gill|1977}}.

==Bibliographie==
*{{Computational Complexity (Arora et Barak)|numéro chapitre=7}}
*{{Article
 | langue                 =  en
 | prénom1                = John
 | nom1                   = Gill
 | lien auteur1           = 
 | titre                  = Computational complexity of probabilistic Turing machines
 | périodique             = SIAM Journal on Computing
 | lien périodique        =  
 | volume                 = 6
 | numéro                 = 4
 | jour                   = 
 | mois                   = 
 | année                  = 1977
 | pages                  = 675-695
 | issn                   = 
 | url texte              = 
 | consulté le            = 
 | id                     = 
}}

==Lien externe==
{{Complexity Zoo|fin=R#rp|nom=RP}}

==Notes et références==
<references />

{{Palette|Théorie de la complexité}}

{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]