1
$\begingroup$

I have a question about cook reductions and karp reductions. Which is the stronger form?

As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp reductions, however with the notion of karp reductions in using nondeterministic polynomial time, doesn't the nondeterministic part mean that it's not necessarily polynomial as we could end up listing all possible inputs as the certificate? Whereas cook reductions require the reduction to be done in a polynomial number of steps so surely a cook reduction would be better in this sense, but then a karp reduction is always used after cook reductions.

I realise this isn't really a clear question, but my main question is what is the real difference and why do we need both? Why could we not just use karp reductions for everything? As with every search problem we can just re-phrase it to make it into a decision problem rather than use a cook reduction.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I encourage you to read standard resources on these kinds of reductions; they'll help clear up some possible confusions. en.wikipedia.org/wiki/Polynomial-time_reduction, en.wikipedia.org/wiki/Turing_reduction, en.wikipedia.org/wiki/…, cs.stackexchange.com/q/16386/755, cs.stackexchange.com/q/11120/755, cs.stackexchange.com/q/16371/755, cstheory.stackexchange.com/q/138/5038. That might help give a better sense of what's going on and might help ask a more focused question. $\endgroup$
    – D.W. ♦
    Commented Jun 7, 2016 at 15:14
  • $\begingroup$ I can't understand what you're asking, beyond the first paragraph. Both Cook and Karp reductions (those are people's names, so they very much deserve their capital letters) are, by definition, performed by deterministic polynomial-time machines. $\endgroup$
    – David Richerby
    Commented Jun 7, 2016 at 15:23
  • $\begingroup$ Having said that, a big part of the answer to your question is probably going to be, "Cook originally defined NP-completeness in terms of what are now called Cook reductions. Karp later proposed what are now called Karp reductions and they're better suited to NP-completeness because of XYZ. Cook reductions are mostly historical, at this point, at least with respect to NP-completeness." $\endgroup$
    – David Richerby
    Commented Jun 7, 2016 at 15:25
  • $\begingroup$ The answer is probably "because people define whatever they please, then the field grows organically, and some things are used more than others". $\endgroup$
    – Raphael
    Commented Jun 7, 2016 at 20:16

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.