MO417 - Questão para a prova oral
Número: 2003-172Enunciado: Sobre problemas NP-Completos é correto afirmar que:
- Um problema que pode ser resolvido em tempo polinomial em um certo modelo de computação jamais pode ser resolvido em tempo polinomial em outro modelo.
- Os problemas de decisão não permitem o uso de mecanismos da teoria de linguagens formais.
- O adjetivo "NP-Completo" se aplica somente a problemas de otimização.
- São problemas cuja complexidade é desconhecida.
- N.D.A.
Ideia original de: Daniele Constant Guimarães
Nenhum comentário:
Postar um comentário