RP (complexité) - RP (complexity)

Dans la théorie de la complexité computationnelle , le temps polynomial aléatoire ( RP ) est la classe de complexité des problèmes pour lesquels une machine de Turing probabiliste existe avec ces propriétés :

• Il s'exécute toujours en temps polynomial dans la taille d'entrée
• Si la bonne réponse est NON, elle renvoie toujours NON
• Si la bonne réponse est OUI, alors il renvoie OUI avec une probabilité d'au moins 1/2 (sinon, il renvoie NON).

En d'autres termes, l' algorithme est autorisé à lancer une pièce vraiment aléatoire pendant son exécution. Le seul cas dans lequel l'algorithme peut retourner OUI est si la réponse réelle est OUI ; donc si l'algorithme se termine et produit OUI, alors la bonne réponse est définitivement OUI ; cependant, l'algorithme peut se terminer par NON quelle que soit la réponse réelle. C'est-à-dire que si l'algorithme renvoie NON, cela peut être faux.

Certains auteurs appellent cette classe R , bien que ce nom soit plus couramment utilisé pour la classe des langages récursifs .

Si la bonne réponse est OUI et que l'algorithme est exécuté n fois avec le résultat de chaque exécution statistiquement indépendant des autres, alors il renverra OUI au moins une fois avec une probabilité d'au moins 1 − 2 ^{− n} . Donc, si l'algorithme est exécuté 100 fois, alors la chance qu'il donne la mauvaise réponse à chaque fois est plus faible que la chance que les rayons cosmiques aient corrompu la mémoire de l'ordinateur exécutant l'algorithme. En ce sens, si une source de nombres aléatoires est disponible, la plupart des algorithmes de RP sont très pratiques.

La fraction 1/2 dans la définition est arbitraire. L'ensemble RP contiendra exactement les mêmes problèmes, même si le 1/2 est remplacé par toute probabilité constante non nulle inférieure à 1 ; ici constant signifie indépendant de l'entrée de l'algorithme.

Définition formelle

Un langage L est dans RP si et seulement s'il existe une machine de Turing probabiliste M , telle que

• M s'exécute pour le temps polynomial sur toutes les entrées
• Pour tout x dans L , M sort 1 avec une probabilité supérieure ou égale à 1/2
• Pour tout x pas dans L , M sorties 0

Alternativement, RP peut être défini en utilisant uniquement des machines de Turing déterministes. Un langage L est dans RP si et seulement s'il existe un polynôme p et une machine de Turing déterministe M , tels que

• M s'exécute pour le temps polynomial sur toutes les entrées
• Pour tout x dans L , la fraction de chaînes y de longueur p (| x |) qui satisfont est supérieure ou égale à 1/2${\style d'affichage M(x,y)=1}$
• Pour tout x non dans L , et toutes les chaînes y de longueur p (| x |),${\style d'affichage M(x,y)=0}$

Dans cette définition, la chaîne y correspond à la sortie des lancers aléatoires que la machine de Turing probabiliste aurait fait. Pour certaines applications, cette définition est préférable car elle ne mentionne pas les machines de Turing probabilistes.

Classes de complexité associées

RP par rapport à d'autres classes de complexité probabilistes ( ZPP , co-RP , BPP , BQP , PP ), qui généralisent P au sein de PSPACE . On ne sait pas si l'un de ces confinements est strict.

La définition de RP dit qu'une réponse OUI est toujours correcte et qu'une réponse NON peut être fausse, car une instance OUI peut renvoyer une réponse NON. La classe de complexité co-RP est le compliment, où une réponse OUI peut être fausse alors qu'une réponse NON est toujours correcte.

La classe BPP décrit des algorithmes qui peuvent donner des réponses incorrectes sur les instances OUI et NON, et contient donc à la fois RP et co-RP . L'intersection des ensembles RP et co-RP est appelée ZPP . Tout comme RP peut être appelé R , certains auteurs utilisent le nom co-R plutôt que co-RP .

Connexion à P et NP

P est un sous-ensemble de RP , qui est un sous-ensemble de NP . De même, P est un sous-ensemble de co-RP qui est un sous-ensemble de co-NP . On ne sait pas si ces inclusions sont strictes. Cependant, si la conjecture communément admise P = BPP est vraie, alors RP , co-RP et P s'effondrent (sont tous égaux). En supposant en outre que P ≠ NP , cela implique alors que RP est strictement contenue dans NP . On ne sait pas si RP = co-RP , ou si RP est un sous-ensemble de l'intersection de NP et co-NP , bien que cela soit impliqué par P = BPP .

Un exemple naturel d'un problème dans co-RP actuellement pas connu pour être dans P est le test d'identité polynomiale , le problème de décider si une expression arithmétique multivariée donnée sur les entiers est le zéro-polynôme. Par exemple, x · x − y · y − ( x + y )·( x − y ) est le polynôme zéro alors que x · x + y · y ne l'est pas.

Une caractérisation alternative de RP qui est parfois plus facile à utiliser est l'ensemble des problèmes reconnaissables par les machines de Turing non déterministes où la machine accepte si et seulement si au moins une fraction constante des chemins de calcul, indépendante de la taille d'entrée, accepte. NP, en revanche, n'a besoin que d'un seul chemin acceptant, qui pourrait constituer une fraction exponentiellement faible des chemins. Cette caractérisation rend évident le fait que RP est un sous-ensemble de NP .

Voir également

• Algorithme aléatoire
• BPP
• ZPP

Les références

Liens externes

• RP au Complexity Zoo