Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Assinale a alternativa correta a respeito dessa classificação de problemas.

Vamos analisar cada alternativa usando as definições de classes de complexidade.

Conceitos-chave

• P: problemas decidíveis/resolvíveis em tempo polinomial por algoritmo determinístico.
• NP: problemas cujas soluções (certificados) podem ser verificadas em tempo polinomial.
• NP-difícil (NP-hard): problemas pelo menos tão difíceis quanto qualquer problema de NP (todo problema de NP reduz-se a ele em tempo polinomial). Um problema NP-difícil não precisa estar em NP.
• NP-completo (NP-complete): problemas que estão em NP e são NP-difíceis ao mesmo tempo.

Agora, as alternativas:

a) “Encontrar a rota ótima … é um problema da classe P.”

• Isso descreve o Problema do Caixeiro Viajante (TSP) na versão de otimização, que é classicamente NP-difícil. A versão de decisão (“existe rota com custo ≤ K?”) é NP-completa. Portanto, não é correto afirmar que é P.

b) “Qualquer problema NP-difícil é possível de ter um certificado verificado em tempo polinomial.”

• Verificação polinomial de certificado é característica de NP, não de NP-difícil. Como um problema NP-difícil pode nem estar em NP, essa afirmação é falsa.

c) “Para todo problema cuja solução pode ser testada em tempo polinomial, existe um algoritmo polinomial que o resolva.”

• Isso equivaleria a afirmar P = NP (ou algo muito próximo no contexto). Como não se sabe se $P=NP$, a afirmação não pode ser dada como verdadeira.

d) “Todo problema que é NP-completo, mas não é NP-difícil …”

• Isso é contraditório: por definição, se é NP-completo, então é NP-difícil. Logo, a alternativa é falsa.

e) “A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP verdadeira.”

• Se um problema NP-completo tivesse algoritmo polinomial, então (por reduções polinomiais) todo problema em NP também teria algoritmo polinomial, implicando $P = NP$. Portanto, esta é a correta.

Alternativa correta: (e).