Assunto: Fluxo máximo e Problemas NP-Completos

Questão para a prova oral 172

Enunciado
Sobre problemas NP-Completos é correto afirmar que:

A) Um problema que pode ser resolvido em tempo polinomial para um modelo jamais pode ser resolvido em tempo polinomial em outro modelo.
B) Os problemas de decisão não permitem o uso do mecanismo da teoria de linguagem formal.
C) O adjetivo NP-Completo se aplica somente a problemas de otimização.
D) São problemas cuja complexidade é desconhecida.
E) N.D.A.

Autor: Daniele Constant Guimarães
RA: 012108