MO417 - Questão para a prova oral

Número: 2010-110

Enunciado: Considere as classes de problemas P, NP, NP-difícil e NP-completo e os seguintes procedimentos:

I. Encontrar um algoritmo determinístico polinomial para algum problema em NP.
II. Encontrar um algoritmo determinístico polinomial para algum problema em NP-difícil.
III. Encontrar um algoritmo determinístico polinomial para algum problema em NP-completo

Para provar que P = NP:

1. Apenas os procedimentos I e II podem ser utilizados.
2. Apenas os procedimentos I e III podem ser utilizados.
3. Apenas os procedimentos II e III podem ser utilizados.
4. Todos os procedimentos podem ser utilizados.
5. NDA

Ideia original de: Marcos Vinícius Mussel Cirne