<blockquote>
  <p><strong>Possible Duplicates:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc">Do many-one reductions and Turing reductions define the same class NPC</a><br>
  <a href="https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc">Many-one reductions vs. Turing reductions to define NPC</a>  </p>
</blockquote>



<p>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.</p>

CC BY-SA 2.5
2010-11-26T14:27:38.187Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-11-26T16:14:33.627Z
Note that problem $P$ plays no real part in your question, you may as well replace it by SAT.
András Salamon
CC BY-SA 2.5
2010-11-26T16:35:47.093Z
@András: Why is UNSAT NP-complete under Cook reducibility?  If I am not mistaken, it implies that UNSAT∈NP (by definition of NP-completeness) and therefore it cannot happen unless NP=coNP.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-26T17:03:09.630Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-26T17:12:36.423Z
I agree with Peter, this is interesting question.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-26T17:26:15.247Z
@Peter: No one has argued that this is not a real question.  This question should be closed because it is an exact duplicate of the [existing question](http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc).  Answers should be posted on the other page, not here.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-26T17:32:07.783Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-26T17:39:43.907Z
@Tsuyoshi: O.K. I agree with you now. I somehow was thinking András had said "hard" and not "complete".
Peter Shor 
CC BY-SA 2.5
2010-11-26T21:51:30.540Z
Have removed my incorrect comment above: as Peter points out, UNSAT is not in NP.
András Salamon
CC BY-SA 2.5
2010-11-26T22:14:35.457Z
Related: [many-one reductions vs Turing-reductions to define NPC](http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc)
Kaveh
CC BY-SA 2.5
2010-11-26T23:02:57.533Z
@Tsuyoshi: The "duplicate" question is actually two *different* questions which the OP seems to think are the same. While the answers to that question are fairly reasonable, is it a good idea to leave that as the question of record on this topic?
Peter Shor 
CC BY-SA 2.5
2010-11-27T12:46:22.613Z
I fixed the duplicate question http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc by changing it's wording, and now I feel O.K. about closing this one.
Peter Shor 
<cc.complexity-theory><open-problem><reductions>
Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions?
Bart Jansen
# Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions?

(Asked by: username_0 on 2010-11-26)

> **Possible Duplicates:**  
> [Do many-one reductions and Turing reductions define the same class NPC](https://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc)  
> [Many-one reductions vs. Turing reductions to define NPC](https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc)

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.

**Tags:** cc.complexity-theory, open-problem, reductions
> **Comments:**
> **username_1**: 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.  
> **username_2**: Note that problem $P$ plays no real part in your question, you may as well replace it by SAT.  
> **username_3**: @András: Why is UNSAT NP-complete under Cook reducibility?  If I am not mistaken, it implies that UNSAT∈NP (by definition of NP-completeness) and therefore it cannot happen unless NP=coNP.  
> **username_4**: 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.  
> **username_5**: I agree with Peter, this is interesting question.  
> **username_3**: @Peter: No one has argued that this is not a real question.  This question should be closed because it is an exact duplicate of the [existing question](http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc).  Answers should be posted on the other page, not here.  
> **username_3**: @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.  
> **username_4**: @Tsuyoshi: O.K. I agree with you now. I somehow was thinking András had said "hard" and not "complete".  
> **username_2**: Have removed my incorrect comment above: as Peter points out, UNSAT is not in NP.  
> **username_6**: Related: [many-one reductions vs Turing-reductions to define NPC](http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc)  
> **username_4**: @Tsuyoshi: The "duplicate" question is actually two *different* questions which the OP seems to think are the same. While the answers to that question are fairly reasonable, is it a good idea to leave that as the question of record on this topic?  
> **username_4**: I fixed the duplicate question http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc by changing it's wording, and now I feel O.K. about closing this one.  

---

## 0 answers

