Co dowody na to, że

Co dowody na to, że ?$coRP \neq NP$

jest klasą języków, dla których istnieje probabilistyczna maszyna Turinga, która działa w czasie wielomianowym i zawsze odpowiada Tak na dane wejściowe należące do języka i odpowiada Nie z prawdopodobieństwem co najmniej połowy na dane wejściowe nienależące do języka .$coRP$

Rozważając siłę niedeterminizmu (P vs NP), randomizacja wydaje się kwestią drugiego rzędu. W szczególności, gdy myślimy o „P = NP?” naprawdę interesuje nas pytanie „czy wszystkie problemy NP są możliwe do rozwiązania”, w których można pozwolić na randomizację, więc zdolność do traktowania naprawdę oznacza „w BPP”. Tak więc „NP zawarty w BPP” wydaje się zasadniczo tak mało prawdopodobny jak „P = NP”, a w rzeczywistości, jeśli uznano by je za różne, ludzie bardziej by dbali o to pierwsze, a nie drugie. (Osobliwy wariant „NP w coRP” jest formalnie gdzieś pośrodku między tymi dwoma, ale koncepcyjnie zasadniczo taki sam). Jeśli istnieją wystarczająco dobre generatory pseudolosowe, oba pytania są formalnie takie same. Podobnie w „niejednolitych ustawieniach” wiadomo, że randomizacja nie pomaga, a zatem „

Jeśli przez coR masz na myśli coRP, to wielu uważa, że ​​P = RP = coRP = BPP, a także, że P nie jest równy NP, a zatem coRP nie jest równy NP.

Bardziej bezpośrednio, jeśli NP byłyby równe coRP, to byłby zawarty w coNP (ponieważ coRP jest zawarty w coNP). Następnie przez symetrię, NP = coNP. Oznaczałoby to, że hierarchia wielomianowa upada na pierwszy poziom. Powszechnie uważa się jednak, że hierarchia wielomianowa jest nieskończona.

Aby uniknąć powielania dyskusji na ten sam temat, jest to ściśle związane z poprzednim pytaniem:

Jakie konkretne dowody istnieją dla P = RP?

Krótko mówiąc, P = BPP wynika z założeń twardości, a P = BPP oznacza P = coRP.