012-2006

MO640 - Questão para a prova oral
Número: 012
Enunciado:
A respeito de classes de problemas, podemos afirmar que:

1. Problemas da classe NP não podem ser resolvidos em tempo polinomial.
2. Qualquer problema NP pode ser reduzido em tempo polinomial a um problema NP-completo.
3. Há uma intersecção entre as classes de problemas P e NP, que não engloba completamente nenhuma das duas.
4. As classes de problemas P e NP são comprovadamente diferentes.
5. NDA

Autor(a): Tiago Rinck Caveden