RP (complexidade) - RP (complexity)
Na teoria da complexidade computacional , o tempo polinomial aleatório ( RP ) é a classe de complexidade dos problemas para os quais existe uma máquina de Turing probabilística com estas propriedades:
| Algoritmo RP (1 execução) | ||
|---|---|---|
|
Resposta produzida
Resposta correta |
sim | Não |
| sim | ≥ 1/2 | ≤ 1/2 |
| Não | 0 | 1 |
| Algoritmo RP ( n execuções) | ||
|
Resposta produzida
Resposta correta |
sim | Não |
| sim | ≥ 1 - 2 - n | ≤ 2 - n |
| Não | 0 | 1 |
| algoritmo co-RP (1 execução) | ||
|
Resposta produzida
Resposta correta |
sim | Não |
| sim | 1 | 0 |
| Não | ≤ 1/2 | ≥ 1/2 |
- Ele sempre roda em tempo polinomial no tamanho de entrada
- Se a resposta correta for NÃO, sempre retorna NÃO
- Se a resposta correta for SIM, ele retorna SIM com probabilidade de pelo menos 1/2 (caso contrário, retorna NÃO).
Em outras palavras, o algoritmo pode lançar uma moeda verdadeiramente aleatória enquanto está em execução. O único caso em que o algoritmo pode retornar SIM é se a resposta real for SIM; portanto, se o algoritmo termina e produz SIM, então a resposta correta é definitivamente SIM; entretanto, o algoritmo pode terminar com NÃO, independentemente da resposta real. Ou seja, se o algoritmo retornar NÃO, pode estar errado.
Alguns autores chamam essa classe de R , embora esse 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, ele retornará SIM pelo menos uma vez com probabilidade de pelo menos 1 - 2 - n . Portanto, se o algoritmo for executado 100 vezes, a chance de ele dar a resposta errada todas as vezes é menor do que a chance de os raios cósmicos corromperem a memória do computador que está executando o algoritmo. Nesse sentido, se uma fonte de números aleatórios estiver disponível, a maioria dos algoritmos em RP é altamente prática.
A fração 1/2 na definição é arbitrária. O conjunto RP conterá exatamente os mesmos problemas, mesmo que 1/2 seja substituído por qualquer probabilidade constante diferente de zero menor que 1; aqui constante significa independente da entrada para o algoritmo.
Definição formal
Uma linguagem L está em RP se e somente se existe uma máquina de Turing probabilística M , tal que
- M é executado para o tempo polinomial em todas as entradas
- Para todo x em L , M produz 1 com probabilidade maior ou igual a 1/2
- Para todos os x não em L , M produz 0
Alternativamente, RP pode ser definido usando apenas máquinas de Turing determinísticas. Uma linguagem L está em RP se e somente se existe um polinômio p e uma máquina de Turing determinística M , tal que
- M é executado para o tempo polinomial em todas as entradas
- Para todo x em L , a fração das cordas y de comprimento p (| x |) que satisfazem é maior ou igual a 1/2
- Para todos os x não em L , e todas as strings y de comprimento p (| x |),
Nessa definição, a string y corresponde à saída dos lançamentos aleatórios de moeda que a máquina de Turing probabilística teria feito. Para algumas aplicações, esta definição é preferível, uma vez que não menciona máquinas de Turing probabilísticas.
Classes de complexidade relacionadas
A definição de RP diz que uma resposta SIM está sempre certa e que uma resposta NÃO pode estar errada, pois uma instância SIM pode retornar uma resposta NÃO. A classe de complexidade co-RP é o elogio, onde uma resposta SIM pode estar errada, enquanto uma resposta NÃO está sempre certa.
A classe BPP descreve algoritmos que podem fornecer respostas incorretas em ambas as instâncias SIM e NÃO e, portanto, contém RP e co-RP . A interseção dos conjuntos RP e co-RP é chamada ZPP . Assim como RP pode ser chamado de R , alguns autores usam o nome co-R em vez de co-RP .
Conexão com P e NP
P é um subconjunto de RP , que é um subconjunto de NP . Da mesma forma, P é um subconjunto de co-RP, que é um subconjunto de co-NP . Não se sabe se essas inclusões são estritas. No entanto, se a conjectura comumente aceita P = BPP for verdadeira, então RP , co-RP e P entram em colapso (são todos iguais). Supondo, além disso, que P ≠ NP , isso implica que RP está estritamente contido em NP . Não se sabe se RP = co-RP ou se RP é um subconjunto da interseção de NP e co-NP , embora isso esteja implícito em P = BPP .
Um exemplo natural de um problema em co-RP atualmente não conhecido por estar em P é o Teste de Identidade Polinomial , o problema de decidir se uma dada expressão aritmética multivariada sobre os inteiros é o polinômio zero. Por exemplo, x · x - y · y - ( x + y ) · ( x - y ) é o polinômio zero, enquanto x · x + y · y não é.
Uma caracterização alternativa de RP que às vezes é mais fácil de usar é o conjunto de problemas reconhecíveis por máquinas de Turing não determinísticas onde a máquina aceita se e somente se pelo menos alguma fração constante dos caminhos de computação, independente do tamanho de entrada, aceita. NP, por outro lado, precisa de apenas um caminho de aceitação, que pode constituir uma fração exponencialmente pequena dos caminhos. Essa caracterização torna óbvio o fato de RP ser um subconjunto de NP .