5) 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 os conteúdos estudados, assinale a alternativa correta a respeito dessa classificação de problemas.
a) Qualquer problema NP-difícil é possível de ter um certificado verificado em tempo polinomial.
b) A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP verdadeira.
c) Encontrar a rota ótima para um trajeto de entrega de mercadorias em pontos específicos é um problema da classe P.
d) Todo problema que é NP-completo, mas não é NP-difícil, pode ter um algoritmo polinomial que o resolva.
e) Para todo problema cuja solução possa ser testada em tempo polinomial, existe um algoritmo polinomial que o resolve.
Soluções para a tarefa
Resposta:
A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP verdadeira
Explicação:
O problema de encontrar uma rota ótima visitando pontos específicos uma única vez é uma aplicação do problema do Caixeiro Viajante, que é da classe NP. Problemas da classe NP-difícil satisfazem apenas uma condição dos problemas da classe NP (problemas NP-completo satisfazem às duas condições e são NP-difíceis), ou seja, se um algoritmo polinomial for encontrado para ele, então todos os problemas NP poderão ser reduzidos a esse problema, o que possibilitará que estes sejam resolvidos em tempo polinomial.
Resposta:
E.
A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP verdadeira.
Explicação:
Acabei de fazer.