RP (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La classe RP, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision sur machine de Turing probabiliste. L'acronyme RP vient de Randomized Polynomial time.

On peut aussi définir une classe très proche : co-RP.

Définition[modifier | modifier le code]

Une première définition[modifier | modifier le code]

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 coté".

Définition formelle[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Avec les classes "classiques"[modifier | modifier le code]

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

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

Avec les autres classes probabilistes[modifier | modifier le code]

Inclusions de classes de complexité 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 cotés").

Problèmes dans RP et co-RP[modifier | modifier le code]

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, a décidé s'il est identiquement nul ou non. Grâce au lemme de Schwartz–Zippel (en), on peut reconnaître les polynômes nuls avec une bonne probabilité en les évaluant en un petit nombre de points.

Histoire[modifier | modifier le code]

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

Bibliographie[modifier | modifier le code]

  • (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, no 4,‎ 1977, p. 675-695

Lien externe[modifier | modifier le code]

(en) La classe RP sur le Complexity Zoo

Notes et références[modifier | modifier le code]

  1. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7), chap. 7
  2. Complexity Zoo