Welche Beweise gibt es dafür, dass

Welche Beweise gibt es dafür, dass ?$coRP \neq NP$

ist die Klasse von Sprachen, für die es eine probabililistische Turing-Maschine gibt, die in Polynomzeit läuft und bei einer Eingabe, die zur Sprache gehört, immer mit Ja und bei einer Eingabe, die nicht zur Sprache gehört, mit mindestens der Hälfte mit Nein antwortet .$coRP$

Wenn man die Macht des Nichtdeterminismus (P vs NP) betrachtet, scheint die Randomisierung ein Problem 2. Ordnung zu sein. Insbesondere wenn wir an "P = NP?" Wir sind wirklich interessiert an der Frage "Sind alle NP-Probleme nachvollziehbar?", wo Randomisierung erlaubt sein könnte, also bedeutet Nachvollziehbarkeit wirklich "in BPP". "NP in BPP enthalten" scheint also im Wesentlichen so unwahrscheinlich wie "P = NP", und wenn diese als unterschiedlich angesehen würden, würden sich die Menschen eher für das erstere als für das letztere interessieren. (Die eigentümliche Variante "NP in coRP" liegt formal irgendwo in der Mitte zwischen diesen beiden, aber konzeptionell im Wesentlichen gleich). Wenn gut genug Pseudozufallsgeneratoren existieren, sind die beiden Fragen formal gleich. In ähnlicher Weise ist bekannt, dass in "uneinheitlichen Einstellungen" Randomisierung nicht hilft und somit "

Wenn mit coR coRP gemeint ist, dann wird von vielen angenommen, dass P = RP = coRP = BPP ist und dass P nicht gleich NP ist, also ist coRP nicht gleich NP.

Wenn NP gleich coRP wäre, wäre es direkter in coNP enthalten (da coRP in coNP enthalten ist). Dann ist durch Symmetrie NP = coNP. Dies würde bedeuten, dass die Polynomhierarchie auf die erste Ebene zusammenbricht. Es wird jedoch allgemein angenommen, dass die Polynomhierarchie unendlich ist.

Um eine doppelte Diskussion desselben Themas zu vermeiden, hängt dies sehr eng mit einer früheren Frage zusammen:

Welche spezifischen Beweise gibt es für P = RP?

Kurz gesagt, P = BPP folgt aus Härteannahmen, und P = BPP impliziert P = coRP.