RP Randomizados em tempo polinomial é a complexidade classe de complexidade computacional teoria, problemas para os quais uma máquina de Turing probabilística existe com estas propriedades:⁕sempre é executado em tempo polinomial no tamanho da entrada⁕Se a resposta correta é NÃO, ele sempre retorna NENHUM⁕Se a resposta correta é SIM, então ele retorna SIM com probabilidade de pelo menos 1/2.Em outras palavras, o algoritmo pode virar um aleatórios moeda enquanto ele está sendo executado. O único caso em que o algoritmo pode retornar sim é se a resposta real é sim; portanto, se o algoritmo termina e produz sim, então a resposta correta é definitivamente Sim; No entanto, o algoritmo pode terminar com não, independentemente da resposta real. Isto é, se o algoritmo retornar não, pode estar errado.Alguns autores chamam esta classe R, Embora este nome seja mais comumente usado para a classe de linguagens recursivas.Se a resposta correta for sim e o algoritmo for executado n vezes com o resultado de cada execução estatisticamente independente dos outros, então ele retornará sim pelo menos uma vez com probabilidade pelo menos 1 − 2−. Então se o algoritmo é executado 100 vezes, então a chance de dar a resposta errada todas as vezes é menor do que a chance de que os raios cósmicos corromperam a memória do computador executando o algoritmo. Neste sentido, se uma fonte de Números Aleatórios está disponível, a maioria dos algoritmos em PR são altamente práticos.

ver mais ”