Quelles sont les preuves que ?

Quelles sont les preuves que ?$coRP \neq NP$

$coRP$ est la classe de langues pour laquelle il existe une machine de Turing probabiliste qui fonctionne en temps polynomial et répond toujours Oui sur une entrée appartenant à la langue et répond Non avec une probabilité d'au moins la moitié sur une entrée n'appartenant pas à la langue.

Lorsque l'on considère la puissance du non-déterminisme (P vs NP), la randomisation semble être un problème de second ordre. En particulier quand on pense à "P = NP?" nous sommes vraiment intéressés par la question "tous les problèmes de NP sont-ils traitables", où la randomisation pourrait être autorisée, donc la tractabilité signifie vraiment "dans le BPP". Ainsi, "NP contenu dans BPP" semble essentiellement aussi peu probable que "P = NP", et en fait si ceux-ci étaient considérés comme différents, alors les gens se soucieraient des premiers plutôt que des seconds. (La variante particulière "NP in coRP" est formellement quelque part au milieu entre ces deux, mais conceptuellement essentiellement la même). S'il existe suffisamment de générateurs pseudo aléatoires, les deux questions sont formellement les mêmes. De même, dans les "paramètres non uniformes", la randomisation est connue pour ne pas aider et donc "

Si par coR vous voulez dire coRP, alors beaucoup pensent que P = RP = coRP = BPP, et aussi que P n'est pas égal à NP, donc coRP n'est pas égal à NP.

Plus directement, si NP était égal à coRP, alors il serait contenu dans coNP (puisque coRP est contenu dans coNP). Puis par symétrie, NP = coNP. Cela impliquerait que la hiérarchie polynomiale s'effondre au premier niveau. Il est cependant largement admis que la hiérarchie polynomiale est infinie.

Juste pour éviter une discussion en double sur le même sujet, cela est très étroitement lié à une question précédente:

Quelles preuves spécifiques existe-t-il pour P = RP?

En bref, P = BPP découle des hypothèses de dureté, et P = BPP implique P = coRP.