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

## marked as duplicate by Tsuyoshi Ito, András Salamon, Kristoffer Arnsfelt Hansen, Kaveh, Peter Shor Nov 27 '10 at 12:44

• 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. – M.S. Dousti Nov 26 '10 at 14:27
• Note that problem $P$ plays no real part in your question, you may as well replace it by SAT. – András Salamon Nov 26 '10 at 16:14