Question

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 ≤p X. 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.




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




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




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




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




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

Answer 1

Resposta:

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

Explicação:

Observe as definições relacionadas às classes P e NP e veja como elas estão relacionadas com o conceito denotado pelo operador ≤p apresentado.