RP (complexidade computacional)

Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes 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

• Sempre roda em tempo polinomial no tamanho da entrada
• Se a resposta correta é NÃO, ele sempre retorna NÃO
• Se a resposta correta for SIM, então ele tem uma probabilidade de 1/2 de retornar SIM (caso contrario, retorna NÃO).

Em outras palavras, o algoritmo permite jogar uma moeda realmente aleatória enquanto está rodando. O único caso no qual o algoritmo pode retornar SIM é quando a resposta é realmente 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 verdadeira resposta. Ou seja, se o algoritmo retornar NÃO, ele pode estar errado.

Alguns autores chamam essa classe de R, entretanto esse nome é mais comumente usado para a classe das linguagens recursivas.

Se a resposta correta é SIM e o algoritmo for executado n vezes com o resultado de cada execução estatisticamente independente dos outros, então ele vai retornar SIM pelo menos uma vez com uma probabilidade de pelo menos 1 − 2⁻ⁿ. Logo, se o algoritmo executar 100 vezes, então a chance dele retornar a resposta errada todas as vezes é menor do que a chance de que raios cósmicos corrompam a memória do computador que esteja rodando o algoritmo. Dessa forma, se a fonte dos números aleatórios estiver disponível, a maior parte dos algoritmos em RP são altamente práticos.

A fração 1/2 na definição é arbitraria. O conjunto RP conterá exatamente os mesmos problemas, mesmo que 1/2 seja substituída por qualquer probabilidade constante diferente de zero e menor que 1; aqui constante significa independência da entrada do algoritmo.

Classes de complexidade relacionadas

A definição de RP diz que uma resposta NÃO está sempre certa e que uma resposta SIM pode estar errada. A classe de complexidade co-RP é definida de forma similar, exceto que SIM está sempre certo e que NÃO pode estar errado. Em outras palavras, ele aceita instâncias de SIM mas pode tanto aceitar quanto rejeitar instâncias de NÃO. A classe BPP(inglês: Bounded-error Probabilistic Polinomial time) descreve um algoritmo que pode dar respostas incorretas tanto para instâncias de SIM quanto para instâncias de NÃO, e além disso contém ambos 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 ao invés de co-RP.

Conexão com P e NP

P é um subconjunto de RP, que é um subconjunto de NP. Similarmente, P é um subconjunto de co-RP que é um subconjunto de co-NP. Não é sabido se essas inclusões são próprias. Entretanto, se a conjectura comumente tida como verdade P = BPP for realmente verdadeira, então RP, co-RP, e P serão todas iguais. Assumindo ainda que P ≠ NP, RP estaria estritamente contido em NP. Não é sabido se RP = co-RP, ou se RP é um subconjunto da interseção de NP e co-NP, embora isso implicaria que P = BPP.

Um exemplo natural de um problema em co-RP que não se sabe ainda pertencer a P é o Teste de Identidade Polinomial, o problema de decidir se uma expressão aritmética com diversas variáveis sobre os inteiros é um zero-polinomial(i.e. a constante polinomial P(x)=0 e os coeficientes são iguais a 0). Por exemplo, x·x − y·y − (x + y)·(x − y) é um zero-polinomial enquanto x·x + y·y não é.

Uma caracterização alternativa de RP que pode ser mais fácil de utilizar é o conjunto de problema reconhecível por Máquina de Turing não determinísticas onde a máquina aceita se e somente se ao menos uma fração constante dos caminhos de computação, independente do tamanho da entrada, aceitam. NP, por outro lado, só precisa de um caminho de aceitação, que pode ser considerado como uma fração exponencialmente pequena dos caminhos. Essa caracterização torna óbvio o fato de que RP é um subconjunto de NP.

Bibliografia

• M Kukar, I Kononenko (2007). Machine Learning and Data Mining (em inglês). [S.l.]: Woodhead Publishing. 480 páginas 

Ligações externas

• RP at the Complexity Zoo