Reducción de KARP de problemas de optimización a problemas de decisión.

Question

Cuando considera reducciones de cocción, las versiones de decisión y optimización de los problemas son el tiempo polinomial reducible entre sí.

Centrándose en las reducciones de cocción, existe una reducción natural de KARP de la versión de decisión de un problema a la versión de optimización.¿Es el converso también cierto?

Answer 1

Gracias a los comentarios de Yuval Filmus, entiendo que mi pregunta no tiene sentido a medida que se definen las reducciones de KARP para los problemas de decisión.Dado que las reducciones de cocción permiten más freeness, tiene sentido hablar de una reducción de la cocción de un problema de decisión a un problema de optimización, pero esto no es cierto para la reducción de KARP.