Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Essa classificação é impor...

Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Essa classificação é importante, considerando que ela tem efeito direto sobre a viabilidade de construção de um algoritmo útil em cenários práticos. Considerando essas informações e conteúdos estudados, assinale a alternativa correta a respeito dessa classificação de problemas.


A descoberta de um algoritmo polinomial para o problema -completo de um NP pode tornar a igualdade P = NP verdadeira.
A classe P é composta por problemas que não podem ser resolvidos em tempo polinomial.
A classe NP é composta por problemas que podem ser resolvidos em tempo polinomial.