Какие есть доказательства того, что

Какие есть доказательства того, что ?$coRP \neq NP$

$coRP$ - это класс языков, для которых существует вероятностная машина Тьюринга, которая работает за полиномиальное время и всегда отвечает Да на входе, принадлежащем языку, и отвечает Нет с вероятностью, по крайней мере, наполовину на входе, не принадлежащем языку.

При рассмотрении силы недетерминизма (P против NP) рандомизация кажется проблемой 2-го порядка. В частности, когда мы думаем о "P = NP?" нас действительно интересует вопрос «все ли проблемы NP могут быть отслежены», где рандомизация может быть разрешена, поэтому возможность отслеживания действительно означает «в BPP». Таким образом, «NP, содержащийся в BPP», по сути, столь же маловероятен, как и «P = NP», и на самом деле, если бы они считались различными, люди бы заботились о первом, а не о втором. (Своеобразный вариант «NP in coRP» формально находится где-то посередине между этими двумя, но концептуально по сути тот же). Если существуют достаточно хорошие псевдослучайные генераторы, то эти два вопроса формально совпадают. Точно так же в «неоднородных настройках» известно, что рандомизация не помогает и, следовательно,

Если под coR вы подразумеваете coRP, то многие считают, что P = RP = coRP = BPP, а также что P не равно NP, поэтому coRP не равно NP.

Точнее, если бы NP были равны coRP, то они бы содержались в coNP (поскольку coRP содержится в coNP). Тогда по симметрии NP = coNP. Это будет означать, что полиномиальная иерархия разрушается до первого уровня. Однако широко распространено мнение, что полиномиальная иерархия бесконечна.

Просто чтобы избежать повторного обсуждения одной и той же темы, это очень тесно связано с предыдущим вопросом:

Какие конкретные доказательства существуют для P = RP?

Вкратце, P = BPP следует из допущений твердости, а P = BPP подразумевает P = coRP.