MO417 - Questão para a prova oral

Número: 2003-179

Enunciado: Com relação aos problemas NP-completos, assinale a alternativa INCORRETA:

1. A classe P consiste nos problemas que podem ser resolvidos em tempo polinomial.
2. A classe NP consiste nos problemas que são "verificáveis" em tempo polinomial.
3. Nem todo problema em P está em NP.
4. Um bom exemplo de problema NP-completo é determinar se um grafo orientado tem um ciclo hamiltoniano.
5. NDA.

Ideia original de: Eduardo Akira Yonekura