b'\n_START_ARTICLE_\nRP (complexidade computacional)\n_START_SECTION_\nClasses de complexidade relacionadas\n_START_PARAGRAPH_\nA defini\xc3\xa7\xc3\xa3o de RP diz que uma resposta N\xc3\x83O est\xc3\xa1 sempre certa e que uma resposta SIM pode estar errada. A classe de complexidade co-RP \xc3\xa9\xc3\xa9 definida de forma similar, exceto que SIM est\xc3\xa1 sempre certo e que N\xc3\x83O pode estar errado. Em outras palavras, ele aceita inst\xc3\xa2ncias de SIM mas pode tanto aceitar quanto rejeitar inst\xc3\xa2ncias de N\xc3\x83O. A classe BPP(ingl\xc3\xaas: Bounded-error Probabilistic Polinomial time) descreve um algoritmo que pode dar respostas incorretas tanto para inst\xc3\xa2ncias de SIM quanto para inst\xc3\xa2ncias de N\xc3\x83O, e al\xc3\xa9m disso cont\xc3\xa9m ambos RP e co-RP. A interse\xc3\xa7\xc3\xa3o dos conjuntos RP e co-RP \xc3\xa9 chamada ZPP. Assim como RP pode ser chamado de R, alguns autores usam o nome co-R ao inv\xc3\xa9s de co-RP.\n_START_SECTION_\nConex\xc3\xa3o com P e NP\n_START_PARAGRAPH_\nP \xc3\xa9 um subconjunto de RP, que \xc3\xa9 um subconjunto de NP. Similarmente, P \xc3\xa9 um subconjunto de co-RP que \xc3\xa9 um subconjunto de co-NP. N\xc3\xa3o \xc3\xa9 sabido se essas inclus\xc3\xb5es s\xc3\xa3o pr\xc3\xb3prias. Entretanto, se a conjectura comumente tida como verdade P = BPP for realmente verdadeira, ent\xc3\xa3o RP, co-RP, e P ser\xc3\xa3o todas iguais. Assumindo ainda que P \xe2\x89\xa0 NP, RP estaria estritamente contido em NP. N\xc3\xa3o \xc3\xa9 sabido se RP = co-RP, ou se RP \xc3\xa9 um subconjunto da interse\xc3\xa7\xc3\xa3o de NP e co-NP, embora isso implicaria que P = BPP._NEWLINE_Um exemplo natural de um problema em co-RP que n\xc3\xa3o se sabe ainda pertencer a P \xc3\xa9 o Teste de Identidade Polinomial, o problema de decidir se uma express\xc3\xa3o aritm\xc3\xa9tica com diversas vari\xc3\xa1veis sobre os inteiros \xc3\xa9 um zero-polinomial(i.e. a constante polinomial P(x)=0 e os coeficientes s\xc3\xa3o iguais a 0). Por exemplo, x\xc2\xb7x \xe2\x88\x92 y\xc2\xb7y \xe2\x88\x92 (x + y)\xc2\xb7(x \xe2\x88\x92 y) \xc3\xa9 um zero-polinomial enquanto x\xc2\xb7x + y\xc2\xb7y n\xc3\xa3o \xc3\xa9._NEWLINE_Uma caracteriza\xc3\xa7\xc3\xa3o alternativa de RP que pode ser mais f\xc3\xa1cil de utilizar \xc3\xa9 o conjunto de problema reconhec\xc3\xadvel por M\xc3\xa1quina de Turing n\xc3\xa3o determin\xc3\xadsticas onde a m\xc3\xa1quina aceita se e somente se ao menos uma fra\xc3\xa7\xc3\xa3o constante dos caminhos de computa\xc3\xa7\xc3\xa3o, independente do tamanho da entrada, aceitam. NP, por outro lado, s\xc3\xb3 precisa de um caminho de aceita\xc3\xa7\xc3\xa3o, que pode ser considerado como uma fra\xc3\xa7\xc3\xa3o exponencialmente pequena dos caminhos. Essa caracteriza\xc3\xa7\xc3\xa3o torna \xc3\xb3bvio o fato de que RP \xc3\xa9 um subconjunto de NP.'