Enunciado:
Sobre NP-completude é CORRETO afirmar:
A) Problemas NP-completos têm enunciados bem diferentes de problemas que têm algoritmos de tempo polinomial.
B) Caminhos simples mais longos, ciclo hamiltoniano e satisfabilidade 2-CNF são exemplos de problemas NP-completos.
C) Problemas NP-completos são problemas para os quais ainda não têm nenhum algoritmo de tempo polinomial para sua solução. Porém são "verificáveis" em tempo polinomial.
D) O caráter NP-completo se aplica diretamente a problemas de decisão (resposta "sim" ou não"). Contudo, existe uma relação entre problemas de decisão e problemas de otimização.
E) NDA

Autor(a): Fábio Batista Gomes
RA 022256