Pergunta

Wikipedia says

Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely... .

This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but can be solved efficiently by a NTM with oracle access to another NTM?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top