2
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Also, what have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Commented Aug 23, 2016 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$
    – Héctor Andrade
    Commented Aug 24, 2016 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
    Commented Aug 24, 2016 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. ♦
    Commented Aug 24, 2016 at 18:20

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 26, 2016 at 7:28
  • $\begingroup$ Ugh, can you please format this link list a little more nicely? $\endgroup$
    – Raphael
    Commented Aug 26, 2016 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. ♦
    Commented Aug 26, 2016 at 14:49

Your Answer

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

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