MO417 - Questão para a prova oral

Número: 2003-185

Enunciado: Sobre NP-Completude, qual a alternativa incorreta?

1. Uma linguagem NP-difícil pode ser também uma linguagem NP-completa.
2. A classe de complexidade co-NP é definida como o conjunto de linguagens cujo complemento é NP-completa.
3. Saber se P=NP é um problema em aberto, bem como saber se P = NP ∩ co-NP.
4. SAT é NP-completa.
5. NDA

Ideia original de: Augusto Jun Devegili