As classes de computabilidade possibilitam que os problemas sejam organizados de acordo com as suas características de tratabilidade computacional....

As classes de computabilidade possibilitam que os problemas sejam organizados de acordo com as suas características de tratabilidade computacional. Conhecer as relações entre essas classes e os problemas categorizados nelas é de grande importância para projetar algoritmos que possam ser aplicados em cenários reais. Considere um problema Y que pode ser resolvido usando um número polinomial de passos computacionais, acrescido de um número polinomial de chamadas a um outro problema X. Essa relação pode ser denotada por Y ≤ X.p. Isso quer dizer que X é pelo menos tão difícil quanto Y com relação ao tempo polinomial. Sabendo que, se X pode ser resolvido em tempo polinomial, isso vai implicar que Y também pode ser resolvido em tempo polinomial, analise as asserções a seguir e a relação proposta entre elas. I. Se X é um problema NP-completo, então X pode ser resolvido em tempo polinomial se, e somente se, P = NP. Porque: II. Nesse caso, qualquer outro problema Y pertencente a NP poderá ser resolvido em tempo polinomial. A seguir, assinale a alternativa correta.

I. Se X é um problema NP-completo, então X pode ser resolvido em tempo polinomial se, e somente se, P = NP.
Porque: II. Nesse caso, qualquer outro problema Y pertencente a NP poderá ser resolvido em tempo polinomial.
a) As asserções I e II são proposições falsas.
b) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
c) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
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 verdadeiras, mas a II não é uma justificativa correta da I.