MO417 - Questão para a prova oral

Número: 2003-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:

1. Tentar encontrar um algoritmo que ache uma resposta, que pode não ser ótima, mas tem alguma garantia de ser próxima da solução ótima. 
2. Tentar encontrar um algoritmo que funciona bem na média, mas não necessariamente para todos os casos (na prática o algoritmo atenderá muitos casos satisfatoriamente).
3. Verificar se não é possível restringi-lo (por exemplo, ao invés de considerar tanto grafos orientados quanto não orientados, restringe-se o problema a grafos orientados), de forma que uma solução para este problema restrito possa ser calculada em tempo polinomial.
4. Procurar uma redução do problema para um outro problema para o qual já se sabe calcular uma resposta em tempo polinomial.
5. NDA.

Ideia original de: Ricardo Luís Lachi