Existe um grande debate sobre como tratar e resolver problemas NP- completos. As teorias existentes atualmente, desde a introdução do estudo execut...

Existe um grande debate sobre como tratar e resolver problemas NP- completos. As teorias existentes atualmente, desde a introdução do estudo executado por Stephen Cook (1971) e da prova teórica desenvolvida por Karp (1972), afirmam que é possível efetuar uma redução polinomial de um problema NP-completo para um problema pertencente à classe P. Considerando que esses estudos têm implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas. I. A descoberta desses grandes cientistas não implica necessariamente se ter P = NP, pois, para provar que P = NP, basta encontrar um algoritmo polinomial para um único problema NP-completo. PORQUE II. A descoberta dos cientistas mostrou que, uma vez que problemas NP-completos estão em NP, seu tempo de execução é polinomial. Porém, alguns problemas requerem mais tempo de execução para se chegar a uma solução exata. A respeito dessas asserções, assinale a opção correta:
I. A descoberta desses grandes cientistas não implica necessariamente se ter P = NP, pois, para provar que P = NP, basta encontrar um algoritmo polinomial para um único problema NP-completo.
II. A descoberta dos cientistas mostrou que, uma vez que problemas NP-completos estão em NP, seu tempo de execução é polinomial. Porém, alguns problemas requerem mais tempo de execução para se chegar a uma solução exata.
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.