s 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.