Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente

Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente

ENADE 2014 - QUESTÃO 28

Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P.

Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.

I. A descoberta do cientista implica P = NP.

PORQUE

II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.

A respeito dessas asserções, assinale a opção correta.

A) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.

B) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.

C) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.

D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

E) As asserções I e II são proposições falsas.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

GABARITO:

A) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.

QUESTÃO DISPONÍVEL EM:

- Prova Ciências da Computação ENADE 2014 com Gabarito