Questão para a prova oral 178
Augusto Jun Devegili (RA 025620)
Quanto ao assunto Problemas NP-Completos, qual a alternativa incorreta? Considere
"dificuldade" como a pertinência de um problema nas classes P, NP,
NP-completo.
A) Dependendo da codificação da entrada, um algoritmo pode
ser executado em tempo polinomial ou superpolinomial. Portanto, se em um
algoritmo os valores de entrada estão codificados na base 10 e este
algoritmo possui tempo de execução polinomial, codificar a
entrada na base 2 aumenta o tamanho da entrada e faz com que o tempo de execução
deste algoritmo se torne superpolinomial
B) Em problemas de otimização, procura-se uma solução
possível com melhor valor. Em problemas de decisão, as soluções
têm apenas dois valores: 0 ou 1.
C) O algoritmo de redução, quando aplicável a dois problemas,
X e Y (X sendo reduzido a Y), permite que a solução do problema
X seja reduzida à solução do problema Y. Como o algoritmo
de redução é polinomial, conclui-se que X possui a mesma
"dificuldade" de Y
D) Para alguns problemas de otimização, é possível
enunciar um problema de decisão relacionado de tal forma que a "dificuldade"
deste problema de decisão também se aplica ao problema de otimização
relacionado
E) NDA