Является ли открытый вопрос NP = co-NP таким же, как P = NP?

Мне интересно это на основании нескольких мест в Интернете, которые называют co- серьезной открытой проблемой ... но я не могу найти никаких указаний на то, является ли это тем же, что проблема ...Н П П = Н $\sf NP=$$\sf NP$$\sf P=NP$

Нет. Это еще одна открытая проблема и, безусловно, связанная, но другая. Класс сложности co- $\mathsf{NP}$ - это множество языков, дополнения которых находятся в ; то есть множество проблем решения, для которых ответ «нет» имеет детерминированный верификатор полиномиального времени. Так, например, вопрос "Является ли эта формула SAT неудовлетворительной?" Если ответ «нет», то есть некоторое удовлетворяющее назначение переменных, которое доказывает это; это сертификат для верификатора.$\mathsf{NP}$

Вполне возможно , что , тем не менее Н Р = СО- N P .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP} =$$\mathsf{NP}$

Но с другой стороны, если , то N P = co- N P точно. Это происходит потому , что если язык в Р , то его дополнение также в P , так что если P = N P , то , что идет для каждого языка в N P , как хорошо.$\mathsf{P} = \mathsf{NP}$$\mathsf{NP} =$$\mathsf{NP}$$\mathsf{P}$$\mathsf{P}$$\mathsf{P} = \mathsf{NP}$$\mathsf{NP}$

Хороший способ ответить на этот вопрос - использовать полиномиальную иерархию (PH) (см. Также здесь ). Полиномиальная иерархия - это иерархия классов сложности, которая обобщает классы , N P и c o - N P на машины оракула и использует их в качестве шкалы для измерения сложности задач.${\sf P}$${\sf NP}$${\sf co-NP}$

Известно, что если или P = N P, то полиномиальная иерархия разрушается до своего первого уровня.${\sf NP}={\sf co-NP}$${\sf P}={\sf NP}$