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?

$\endgroup$
  • 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 at 7:25
  • $\begingroup$ Thanks. Let me edit the question then removing the last part. $\endgroup$ – usercs May 7 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 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 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 at 11:31
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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