Le temps polynomial randomisé RP est la classe de complexité de la théorie de la complexité informatique, des problèmes pour lesquels une machine de Turing probabiliste existe avec ces propriétés:ItIl s’exécute toujours en temps polynomial dans la taille d’entréeIfSi la bonne réponse est NON, il renvoie toujours NON⁕ Si la bonne réponse est OUI, alors il renvoie OUI avec une probabilité d’au moins 1/2. En d’autres termes, l’algorithme est autorisé à retourner une pièce vraiment aléatoire pendant son exécution. Le seul cas dans lequel l’algorithme peut renvoyer OUI est si la réponse réelle est OUI; par conséquent, 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. Autrement dit, si l’algorithme renvoie NON, cela pourrait ê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 retournera OUI au moins une fois avec une probabilité d’au moins 1 − 2 −. Donc, si l’algorithme est exécuté 100 fois, la chance qu’il donne la mauvaise réponse à chaque fois est inférieure à 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 en RP sont très pratiques.

voir plus «