Redução de KARP de problemas de otimização para problemas de decisão

Question

Quando você considera reduções de cozinheiro, as versões de decisão e otimização dos problemas são o tempo polinomial redutível entre si.

Focando em Reduções Cook, existe uma redução natural de KARP da versão de decisão de um problema para a versão de otimização.É o inverso também verdadeiro?

Answer 1

Graças aos comentários de filmus yuval, entendo que minha pergunta não faz sentido como as reduções de KARP são definidas para problemas de decisão.Como as reduções de Cook permitem mais Freeness, faz sentido falar sobre uma redução de cozinheiro a partir de um problema de decisão para um problema de otimização, mas isso não é verdade para a redução de KARP.