If there exists a Cook reduction of a decision problem $\mathcal{P}_1$ into another decision problem $\mathcal{P}_2$ and also a Cook reduction of $\mathcal{P}_2$ into $\mathcal{P}_1$, then is there also a Karp reduction (a polynomial transformation) between $\mathcal{P}_1$ and $\mathcal{P}_2$ (in both directions)?

These are the definitions I use:

Cook reduction
$\mathcal{P}_1$ polynomially reduces to $\mathcal{P}_2$ if there is a polynomial-time oracle algorithm for $\mathcal{P}_1$ using an oracle for $\mathcal{P}_2$.

Karp reduction
$\mathcal{P}_1=(X_1,Y_1)$ polynomially transforms to $\mathcal{P}_2=(X_2,Y_2)$ if there is a function $f:X_1\rightarrow X_2$ computable in polynomial time such that for all $x\in X_1$, $x\in Y_1$ if and only if $f(x)\in X_2$.

  • 1
    $\begingroup$ Also, what have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Aug 23 '16 at 16:14
  • $\begingroup$ I already edited the question, @RaphaeI get stuck cause my definiton of "NP-hard problem uses reduction (i.e. $\mathcal{P_1}$ is NP-hard if any NP decision problem can be polynomially transformed to $\mathcal{P_1}$", but the definitions that I find in internet uses polynomial reduction instead of polynoimal transformation $\endgroup$ Aug 24 '16 at 11:49
  • 1
    $\begingroup$ It is well known that the two types of reductions are not known to be equivalent and most believe they induce strictly different notions of hardness. See e.g. here and questions linked there, or here. That is probably what most sources are concerned with. However, you have more to work with here: $P_1$ and $P_2$ are equally hard w.r.t Cook reductions. Have you tried using that? What, specifically, have you tried towards (dis)proving the claim yourself? $\endgroup$
    – Raphael
    Aug 24 '16 at 11:57
  • $\begingroup$ Do you mean to restrict $P_1,P_2$ to be in NP, or do you allow them to be arbitrary? $\endgroup$
    – D.W.
    Aug 24 '16 at 18:20

The answer depends on whether you require both of $\mathcal{P}_1,\mathcal{P}_2$ to be in NP or not.

If the problems need not be in NP

Then the answer to your question is "No". There exist problems $\mathcal{P}_1,\mathcal{P}_2$ that are Cook-reducible (in both directions) but not Karp-reducible (in either direction)

In particular, consider $\mathcal{P}_1 = $ HALT (the Halting problem) and $\mathcal{P}_2 = \overline{\mathcal{P}_1}$ (its complement). They are Cook-reducible (you just invoke the oracle and complement its answer), but not Karp-reducible.

(Similarly, if $\textsf{NP} \ne \textsf{coNP}$, then the answer is No: take $\mathcal{P}_1 = $ SAT and $\mathcal{P}_2 = $ TAUTOLOGY, so that $\mathcal{P}_1$ is NP-complete and $\mathcal{P}_2$ is coNP-complete. They're Cook-reducible, but a Karp reduction would prove that $\textsf{NP} = \textsf{coNP}$ via a standard argument.)

If the question is restricted to require both problems to be in NP

Then it's an open question; no one knows whether the answer is "Yes" or "No". See https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction and

  • $\begingroup$ (As an independent matter:) ​ Due to the existence of Ladner's theorem, I would not be surprised if "If P≠NP then there is an NP problem that is not Karp-reducible to its complement." is true and relativizes (although I'm not aware of any such result). ​ ​ ​ ​ $\endgroup$
    – user12859
    Aug 26 '16 at 7:28
  • $\begingroup$ Ugh, can you please format this link list a little more nicely? $\endgroup$
    – Raphael
    Aug 26 '16 at 8:23
  • $\begingroup$ @Raphael, OK, done. While we're on this topic, let me advocate for meta.stackexchange.com/q/251183/160917 -- you might consider upvoting if you think it would help make this kind of answer look a bit nicer. $\endgroup$
    – D.W.
    Aug 26 '16 at 14:49

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.