Pergunta

I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?

Nenhuma solução correta

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