# Turing NP complete but not Karp NP complete?

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?

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

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.
• $\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. – David Richerby May 6 '16 at 2:01