mar

MO417 - Questão para a prova oral

Número:

Enunciado: Analise as seguintes afirmativas e indique a alternativa INCORRETA:

a) Um problema de decisão A que seja NP-difícil pode ser mostrado ser NP-completo exibindo um algoritmo determinista polinomial para A.
b) Apenas problemas de decisão (“sim/não”) podem ser NP-completo.
c) Problemas de otimização podem ser NP-difícil, mas geralmente, se A é um problema de decisão e B um problema de otimização, é bem possível que A é polinomialmente transformável em B.
d) A dificuldade de um problema NP-difícil não é menor do que a dificuldade de um problema
NP-completo
e) NDA

Ideia original de: Marleny Luque Carbajal