MO417 - Questão para a prova oral

Número: 2003-181

Enunciado: Assinale a alternativa CORRETA:

1. Se uma linguagem é NP-Difícil mas não está em NP, então esta linguagem é NP-Completa.
2. Se uma linguagem pertencente a NP puder ser reduzida a uma outra linguagem A em tempo polinomial, então A é NP-completa.
3. Se uma linguagem NP-difícil qualquer puder ser decidida em tempo polinomial, então TODAS as linguagens pertencentes a NP podem ser decididas em tempo polinomial.
4. Para mostrar que uma linguagem A é NP-Difícil, basta reduzir ALGUMA linguagem em NP, para A.
5. E) NDA

Ideia original de: Ricardo Luís Lachi