Questão para a prova oral 175

Enunciado:
Dentre as alternativas abaixo assinale a INCORRETA a respeito de como se lidar com problemas NP-completos do ponto de vista prático:

A) Deve-se tentar encontrar um algoritmo que ache uma resposta, que pode não ser ótima, mas é garantida ser próxima da solução ótima.
B) Deve-se tentar encontrar um algoritmo que funcioa bem na média, mas não necessariamente para todos os casos (na prática o algoritmo atende muitos casos satisfatoriamente).
C) Avaliar o problema NP-completo que se quer resolver e verificar se não é possível delimitá-lo (por exemplo, ao invés de considerar tanto grafos orientados quanto não orientados, delimita-se o problema somente para grafos orientados), de forma que uma solução para esse problema restrito seja possível de ser calculada em tempo polinomial.
D) Deve-se procurar uma redução do problema para um outro problema para o qual já se sabe calcular uma resposta em tempo polinomial.
E) NDA.

Autor: Ricardo Luís Lachi
RA: 972929