Question

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.PORQUEII.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.@ As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.@ As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. Oasserção I é uma proposição verdadeira, e a II é uma proposição falsa.@ A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. O As asserções I e II são proposições falsas.

#ENADE

Answer 1

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

Considerando uma redução polinomial de um problema NP-completo para um problema pertencente à classe P é preciso destacar que P=NP, visto que qualquer problema aberto e fundamental pode ter uma resolução de acordo com o tempo polinomial.

Dessa forma, P=NP é um problema aberto e fundamental da teoria da computação. Por outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser reduzido, em tempo polinomial.

Bons estudos!