Questão para a prova oral 186
Enunciado:
Suponha que o problema A seja NP-difícil. Suponha também que, recentemente, descobriu-se que um problema B, que é NP-completo, pode ser reduzido em tempo polinomial ao problema A. Com base nestas duas informações, podemos afirmar que:
A) Qualquer problema NP-completo pode ser reduzido a A em tempo polinomial, logo, A também é NP-completo.
B) Qualquer problema NP-completo pode ser reduzido a A em tempo polinomial, logo, P = NP.
C) A será NP-completo somente se houver um algoritmo que o decida em tempo polinomial.
D) Podem haver problemas NP-completos que não se reduzem a A em tempo polinomial, logo, a descoberta recente não inclui o problema A na classe NP.
E) NDA