2
$\begingroup$

Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction?

Conversely is there some examples of candidate problems that have Turing reduction to SAT but no known Karp reduction?

$\endgroup$
  • $\begingroup$ very related ​ ​ $\endgroup$ – user12859 May 6 '16 at 5:01
  • $\begingroup$ There are duplicates on this site, too, I guess. $\endgroup$ – Raphael May 6 '16 at 6:10
  • $\begingroup$ I don't know of any, but see this paper. ​ ​ $\endgroup$ – user12859 May 6 '16 at 7:59
  • $\begingroup$ @RickyDemer I think you commented elsewhere that this paper may not be valid. $\endgroup$ – user39969 May 6 '16 at 10:30
5
$\begingroup$

The complement of any NP-complete problem (including SAT itself) is polynomial-time Turing-interreducible with SAT but, there's a Karp reduction if, and only if, NP$\,=\,$co-NP.

$\endgroup$
  • $\begingroup$ what is the explicit reduction? $\endgroup$ – user39969 May 6 '16 at 1:17
  • $\begingroup$ Same as the reduction to SAT and then negate the answer. $\endgroup$ – David Richerby May 6 '16 at 1:59
  • $\begingroup$ Actually what you are saying seems to mean coNP and NP are in P^NP? $\endgroup$ – user39969 May 6 '16 at 2:00
  • 1
    $\begingroup$ $\mathbf{P}^{\mathbf{NP}}$ is, essentially by definition, exactly the class of problems that are polynomial-time Turing-reducible to SAT so, yes, I am saying that. $\endgroup$ – David Richerby May 6 '16 at 2:01
  • $\begingroup$ Could there be another example? $\endgroup$ – user39969 May 6 '16 at 7:43

Your Answer

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