1
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ NP-completeness is a category of decision problems. When we say that an optimization problem is NP-complete, what we really mean is that its decision version is NP-complete. $\endgroup$
    – Yuval Filmus
    May 7, 2020 at 7:25
  • $\begingroup$ Thanks. Let me edit the question then removing the last part. $\endgroup$
    – usercs
    May 7, 2020 at 10:38
  • $\begingroup$ What do you mean by a Karp reduction from the optimization version to the decision version? Can you give a definition or an example? $\endgroup$
    – Yuval Filmus
    May 7, 2020 at 10:44
  • $\begingroup$ Consider the problem of deciding whether there is vertex cover of size less than $\leq k$ and the problem of finding the minimum vertex cover. $\endgroup$
    – usercs
    May 7, 2020 at 11:30
  • 1
    $\begingroup$ You still haven't define what a Karp reduction would be in this context. I know what a Karp reduction is for two decision problems, but that's not the case you're interested in. $\endgroup$
    – Yuval Filmus
    May 7, 2020 at 11:31

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.