A questão em aberto NP = co-NP é igual a P = NP?

Estou pensando isso com base em vários locais online que chamam co- um grande problema em aberto ... mas não consigo encontrar nenhuma indicação sobre se isso é ou não o mesmo que Problema ...$\sf NP=$$\sf NP$$\sf P=NP$

Não. É outro problema em aberto e certamente relacionado, mas diferente. A classe de complexidade co-$\mathsf{NP}$ é o conjunto de idiomas cujos complementos estão em ; isto é, o conjunto de problemas de decisão para os quais uma resposta "não" possui um verificador de tempo polinomial determinístico. Por exemplo, a pergunta "Esta fórmula SAT é insatisfatória?" Se a resposta for "não", existe uma atribuição satisfatória das variáveis ​​que comprova isso; esse é o certificado para o verificador.$\mathsf{NP}$

É possível que , ainda co- .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP} =$$\mathsf{NP}$

Mas por outro lado, se , então co- com certeza. Isso ocorre porque se um idioma está em , seu complemento também está em , portanto, se , isso vale para todos os idiomas em também.$\mathsf{P} = \mathsf{NP}$$\mathsf{NP} =$$\mathsf{NP}$$\mathsf{P}$$\mathsf{P}$$\mathsf{P} = \mathsf{NP}$$\mathsf{NP}$

Uma boa maneira de responder a essa pergunta é usar a hierarquia polinomial (PH) (veja também aqui ). A hierarquia polinomial é uma hierarquia de classes de complexidade que generaliza as classes , N P e c o - N P para máquinas oracle e usa como uma escala para medir a complexidade dos problemas.${\sf P}$${\sf NP}$${\sf co-NP}$

Sabe-se que Se ou P = N P , a hierarquia polinomial entra em colapso para seu primeiro nível.${\sf NP}={\sf co-NP}$${\sf P}={\sf NP}$