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