# Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions? [duplicate]

Let $P,Q \subseteq \Sigma^*$ be languages such that $P$ and $Q$ are both in NP. Assume that $P$ is NP-complete under Karp reductions (there is a polynomial time many-one reduction from 3-SAT to $P$) and there is a Turing-reduction from $P$ to $Q$, i.e. there is a polynomial-time algorithm which decides $P$ when given oracle-access to $Q$. Intuitively this means that deciding $Q$ is as hard as deciding any problem in NP, while at the same time $Q$ is in NP, so Q cannot be harder'' than NP. Does this imply that $Q$ is NP-complete under Karp reductions, i.e. does this imply the existence of a polynomial-time many-one reduction from 3-SAT to Q? Any pointers are much appreciated.

• In summary: $\mathbf{3SAT} \ \le_m^\rm{P} \ \mathbf{P} \ \le_T^\rm{P} \ \mathbf{Q}$, where $\le_m^\rm{P}$ denotes polynomial-time many-one (Karp) reduction, and $\le_T^\rm{P}$ denotes polynomial-time Turing reduction. Nov 26, 2010 at 14:27
• Note that problem $P$ plays no real part in your question, you may as well replace it by SAT. Nov 26, 2010 at 16:14
• Don't close this question. It's a real question. I don't know the answer, and I don't believe anybody else has given the answer, either. Nov 26, 2010 at 17:03
• @Peter: I know the definition of Turing reductions, but you have not explained why UNSAT is NP-complete under Turing reducibility. NP-completeness means that it belongs to NP and it is NP-hard. Nov 26, 2010 at 17:32
• I fixed the duplicate question cstheory.stackexchange.com/questions/686/… by changing it's wording, and now I feel O.K. about closing this one. Nov 27, 2010 at 12:46