A classe NP está fechada sob complemento?

A classe fechada sob complemento ou é desconhecida? Procurei online, mas não consegui encontrar nada.$\sf NP$

A resposta é "desconhecida pela ciência". Sabe-se que P é fechado sob complemento. Portanto, se P = NP, então NP também é fechado sob complemento. Além disso, se NP não estiver fechado no complemento, então P! = NP.

Primeiro, a pergunta que você está fazendo é aberta, pois uma resposta afirmativa mostra que . De fato, é um dos problemas abertos mais importantes da ciência da computação.$\sf NP = coNP$

Se , a classe é fechada sob complemento, pois é. Se, por outro lado, , não podemos dizer se ou não. Observe que implica que a hierarquia polinomial cai para o primeiro nível. No entanto, isso não implicaria que .$\sf P= NP$$\sf NP$$\sf P$$\sf P \not = NP$$\sf NP = coNP$$\sf NP = coNP$$\sf P= NP$

"Toda classe de complexidade determinística (DSPACE (f (n)), DTIME (f (n)) para todos os f (n)) é fechada sob complemento, porque é possível simplesmente adicionar uma última etapa ao algoritmo que reverte a resposta. Isso não funciona para classes de complexidade não determinísticas, porque, se existem caminhos de computação que aceitam e caminhos que rejeitam, e todos os caminhos revertem sua resposta, ainda haverá caminhos que aceitam e caminhos que rejeitam - consequentemente, a máquina aceita em ambos casos ". Fonte

Isso é desconhecido. Uma prova do problema P vs. NP daria uma resposta.