MO417 - Questão para a prova oral

Número: 2003-186

Enunciado: Suponha que a linguagem A seja NP-difícil. Suponha também que, recentemente, descobriu-se que uma linguagem B, que é NP-completa, pode ser reduzida em tempo polinomial a A. Com base nestas duas informações, podemos afirmar que:

1. Qualquer linguagem NP-completa pode ser reduzida a A em tempo polinomial, logo, A também é NP-completa.
2. Qualquer linguagem NP-completa pode ser reduzida a A em tempo polinomial, logo, P = NP. 
3. A será NP-completa somente se houver um algoritmo que a decida em tempo polinomial.
4. Pode haver linguagens NP-completas que não se reduzem a A em tempo polinomial.
5. NDA

Ideia original de: José Augusto Amgarten Quitzau