When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages?

I've read about Karp Reduction mainly used in the Context of reducing a Language:

e.g. L1 $≤_p$ L2

  • 4
    $\begingroup$ I think this question is too broad: listing different uses will create answers that are probably not useful. This kind of thing is better suited for wikis or blogs. (Also, generally, asking for pros and cons of purely mathematical objects is bound to be disappointing.) $\endgroup$ – Raphael Jun 25 '18 at 17:13
  • $\begingroup$ ok, I just dont see the main difference... you can use both to solve a Problem by using another Problem for which a known Solution exists... is that true? $\endgroup$ – simplesystems Jun 25 '18 at 17:39
  • $\begingroup$ Kind of. The type of functions/algorithms is restricted in different ways. Study the definitions and see if you can spot the difference. Hint: reducibility w.r.t one implies the other, but not (always) the reverse. $\endgroup$ – Raphael Jun 25 '18 at 18:33
  • $\begingroup$ Turing reduction can involve algorithms having a huge complexity. We can easily prove that SAT Turing reduces to checking whether the input is 0, for instance; it does not matter that the reduction is exptime. Further, any language $L$ Turing reduces to $\overline{L}$, but this does not hold with Karp reduction. If $A$ Karp reduces to $B$ and $B$ is P (resp. NP/RE), then $A$ is also P (NP/RE) -- this does not hold with Turing reduction. A lot of differences exist between the two reductions. $\endgroup$ – chi Dec 3 '18 at 9:58

The huge difference is that a Turing reduction allows you to call the black-box more than once. Suppose you have the $\mathtt{GraphColor?(G, k)}$ decision problem which tells you if the graph $G$ can be colored with $k$ colors. A Karp reduction only allows you to call this problem exactly once. But a Turing reduction allows you to call $\mathtt{GraphColor?(G, k)}$ a polynomial number of times. So if you want to figure out the chromatic number of the graph, call the function with $k=1, k=2, \ldots$ and so on until you get something that works. To make it more efficient, use binary search instead.


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