Question

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.

Focusing on Cook reductions, there exists a natural Karp reduction from the decision version of a problem to optimization version. Is the converse also true?

Was it helpful?

Solution

Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top