Vamos analisar as alternativas: 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) Resposta correta d) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. e) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. A asserção I afirma que se X é um problema NP-completo, então X pode ser resolvido em tempo polinomial se, e somente se, P = NP. Isso é falso, pois a questão de P ser igual a NP é um dos problemas mais importantes e não resolvidos da ciência da computação. A asserção II afirma que, nesse caso, qualquer outro problema Y pertencente a NP poderá ser resolvido em tempo polinomial. Isso também é falso, pois a igualdade P = NP implicaria que todos os problemas em NP seriam resolúveis em tempo polinomial, o que ainda não foi comprovado. Portanto, a resposta correta é a letra b) As asserções I e II são proposições falsas.
Para escrever sua resposta aqui, entre ou crie uma conta
Linguagens Formais e Automatos
•ESTÁCIO EAD
Compartilhar