Questão para a prova oral 179 (Semana 14: Fluxo máximo II e Problemas NP-completos)
Enunciado:
Com relação aos problemas NP-completos, assinale a alternativa INCORRETA:
A) A classe P consiste nos problemas que podem ser resolvidos em tempo polinomial. A maioria dos algoritmos vistos ao longo do curso é da classe P.
B) A classe NP consiste nos problemas que são "verificáveis" em tempo polinomial.
C) Nem todo problema em P também está em NP.
D) Um bom exemplo de problema NP-completo é determinar se um grafo orientado tem um ciclo hamiltoniano.
E) NDA.