Que evidência existe de que ?

Que evidência existe de que ?$coRP \neq NP$

$coRP$ é a classe de idiomas para a qual existe uma máquina de Turing probabililística que é executada em tempo polinomial e sempre responde Sim em uma entrada pertencente ao idioma e responde Não com probabilidade de pelo menos metade em uma entrada não pertencente ao idioma.

Ao considerar o poder do não determinismo (P vs NP), a randomização parece uma questão de 2ª ordem. Em particular quando pensamos em "P = NP?" estamos realmente interessados ​​na questão "todos os problemas de PN são tratáveis", onde a randomização pode ser permitida; portanto, tratabilidade realmente significa "no BPP". Portanto, "NP contido no BPP" parece essencialmente tão improvável quanto "P = NP" e, de fato, se estes forem considerados diferentes, as pessoas se importariam com o primeiro e não com o último. (A variante peculiar "NP em coRP" está formalmente em algum lugar no meio entre esses dois, mas conceitualmente essencialmente o mesmo). Se existirem geradores pseudo-aleatórios bons o suficiente, as duas perguntas serão formalmente iguais. Da mesma forma, em "configurações não uniformes", sabe-se que a randomização não ajuda e, portanto, "

Se por coR você quer dizer coRP, muitos acreditam que P = RP = coRP = BPP e também que P não é igual a NP, portanto, coRP não é igual a NP.

Mais diretamente, se o PN fosse igual ao coRP, ele estaria contido no coNP (uma vez que o coRP está contido no coNP). Então, por simetria, NP = coNP. Isso implicaria que a hierarquia polinomial entra em colapso para o primeiro nível. No entanto, acredita-se amplamente que a hierarquia polinomial é infinita.

Apenas para evitar discussões duplicadas sobre o mesmo tópico, isso está intimamente relacionado a uma pergunta anterior:

Que evidência específica existe para P = RP?

Em suma, P = BPP segue dos pressupostos de dureza, e P = BPP implica P = coRP.