<p>The <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bh" rel="noreferrer">"Boolean Hierarchy" BP</a> is a whole hierarchy of combinations of NP problems under Karp reductions which are all in P^NP.</p>

CC BY-SA 2.5
2010-08-29T01:15:06.257Z
2010-11-26T23:11:22.327Z
2010-11-26T23:11:22.327Z
Noam
<p>As far as I can tell, this question really comprises two distinct questions, the first of which appears in the title and the second of which is given after the edit.</p>

<p>(1) Do many-one reductions and Turing reductions define the same set of NP-complete problems (i.e. problems that are both in NP and which SAT can be reduced to)? Whether NPC under Turing reductions is the same as NPC under many-one reductions was still an open problem seven years ago, and I don't believe it has been closed since. See <a href="http://www.cs.iastate.edu/~pavan/papers/sigact.pdf">this survey</a> from the June 2003 ACM SIGACT News for details.</p>

<p>(2) What is the class of problems which SAT has a Turing reduction to, and vice versa? This is the class of NP-hard problems (under Turing reductions) which are in P<sup>NP</sup>. For more information on this, see  Noam's answer.</p>

CC BY-SA 3.0
2016-05-05T23:06:13.910Z
link does not work.
Turbo
CC BY-SA 2.5
2010-11-26T20:27:45.463Z
2010-11-27T12:42:47.587Z
2010-11-27T12:42:47.587Z
Peter Shor 
<p>This doesn't answer your question, but one could ask the same question for weaker reductions. For example, does the set of NP-complete problems change if we permit only log space reductions, or only AC<sup>0</sup> reductions, or even NC<sup>0</sup> reductions. A suprising fact is that all known NP-complete problems are complete even with NC<sup>0</sup> reductions. </p>

<p>Reference: Agrawal, M., Allender, E., and Rudich, S. 1997 Reductions in Circuit Complexity: an Isomorphism Theorem and a Gap Theorem.</p>

CC BY-SA 4.0
2022-12-29T17:41:16.160Z
I assume you only mean natural NPC problems, otherwise the NPC solver can request a correct hash input
l4m2
CC BY-SA 2.5
2010-11-26T22:59:30.207Z
Is this question about weaker reductions still open? If I have a problem which was NP complete under P/poly or BPP reductions, but apparently not under P reductions without assuming unproven number theoretic assumptions, is it worth making a note of?
Peter Shor 
CC BY-SA 2.5
2010-11-27T17:07:46.310Z
@Peter: In the paper I've cited, it is left open if there is any problem that is NP-complete under polynomial time reductions which isn't NP-complete under AC^0 reductions. This question has been answered by [Reducing the complexity of reductions](http://www.springerlink.com/content/bbar426549dv33ut/). They show a problem that is NP-complete with ACC reductions but not AC^0 reductions. None of these papers seem to comment on problems that are NP-complete under reductions stronger than polynomial time, and how that relates to the possibility of being NP-complete under polytime reductions.
Robin Kothari
CC BY-SA 2.5
2010-08-28T06:14:31.337Z
2010-08-28T06:14:31.337Z
Robin Kothari
<p>Have a look at this <a href="https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc">this question</a> and especially <a href="https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc/139#139">this answer</a> by Aaron Sterling. In short: "they are conjectured to be distinct notions."</p>

CC BY-SA 2.5
2010-08-27T20:56:25.160Z
I know that if NP!=co-NP, they are distinct notions because Turing reduction collapses them, but could there be differences which wouldn't be collapses, for example a problem in NPI under many-one reduction and in NPC under Turing reduction ?
Ludovic Patey
CC BY-SA 2.5
2010-08-29T12:50:09.477Z
@Monoïd: NP≠coNP does not imply (at least in an obvious way) that the two notions of reductions are distinct.  I am afraid that you are confusing the class NP (which is defined independently of the choice of the notion of reductions) with the class of decision problems reducible to NP (which depends on the choice of the notion of reductions).
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-29T13:30:13.470Z
Oops, my previous comment was wrong.  If NP≠coNP, the two notions of reductions are obviously distinct (SAT is unconditionally Turing reducible to UNSAT, but SAT is many-one reducible to UNSAT if and only if NP=coNP).
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-27T20:19:29.257Z
2010-08-27T20:19:29.257Z
2017-04-13T12:32:28.077Z
Matthias
<p>I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.</p>

<p>Edit:
Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class $C$ such as there exists a problem not in $C \cup co-C$ under Karp reduction and which is in $C$ under Turing reduction ?</p>

CC BY-SA 2.5
2010-08-27T20:12:47.530Z
Have you read http://en.wikipedia.org/wiki/NP-complete#Completeness_under_different_types_of_reduction ?
Jukka Suomela
CC BY-SA 2.5
2010-08-27T21:02:28.827Z
Thank you for your link. It answers to the first part of my question, but doesn't answers wether there are problems which arent in co-C under many-one reduction and are in C under Turing reduction, for any C.
Ludovic Patey
CC BY-SA 2.5
2010-08-27T21:05:02.997Z
Sorry, this may seem an elementary question or maybe I am not thinking straight at this late hour but I am missing something in the wiki article. The article says that under Cook reductions, NP-complete is equal to co-NP-complete, but I don't see it. NP-hard is equal to co-NP-hard w.r.t Cook reductions, but NP-complete means being both *NP-hard* **AND** *NP*, and I don't see why (e.g.) TAUT would be in NP? I.e. TAUT is co-NP-hard under Cook reductions but that is not enough for being NP-complete.
Kaveh
CC BY-SA 2.5
2010-08-27T22:01:41.897Z
@Monoid, you should reword your question to reflect this clarification then. As such the question is ambiguous
Suresh Venkat
CC BY-SA 2.5
2010-08-28T06:15:54.070Z
possible duplicate of [Many-one reductions vs. Turing reductions to define NPC](http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc)
Suresh Venkat
CC BY-SA 2.5
2010-08-28T06:16:26.730Z
voting to close as duplicate of http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc (see mashca's answer below)
Suresh Venkat
CC BY-SA 2.5
2010-08-28T06:40:45.623Z
@Lev: Thanks for the answer but why would TAUT (=UNSAT) be in NP? NP is not known to be closed under Cook (polytime Turing) reductions. The situation seems to be similar to computability theory, replace NP, co-NP, and Cook reduction with r.e., co-r.e., and Turing reductions, and we know that the arithmetical hierarchy provably does not collapse under Turing reductions so I don't see what is different in the NP setting?
Kaveh
CC BY-SA 2.5
2010-08-28T09:16:33.010Z
@Suresh I had already looked at the other question but it didn't answered to mine. I've edited it to be more precise.
Ludovic Patey
CC BY-SA 2.5
2010-08-29T12:54:16.573Z
@Lev Reyzin: The choice of reductions does not affect the definition of the classes NP and coNP!
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-29T13:55:50.307Z
I stand corrected - Cook reductions aren't useful for showing a problem is in NP.
Lev Reyzin
CC BY-SA 2.5
2010-11-29T02:09:18.943Z
@Peter: Thank you for editing the question.  It makes much more sense now.
Tsuyoshi Ito
<cc.complexity-theory><np-hardness><reductions>
Do many-one reductions and Turing reductions define the same class NPC
Ludovic Patey
# Do many-one reductions and Turing reductions define the same class NPC

(Asked by: username_0 on 2010-08-27)

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.

Edit:
Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class $C$ such as there exists a problem not in $C \cup co-C$ under Karp reduction and which is in $C$ under Turing reduction ?

**Tags:** cc.complexity-theory, np-hardness, reductions
> **Comments:**
> **username_1**: Have you read http://en.wikipedia.org/wiki/NP-complete#Completeness_under_different_types_of_reduction ?  
> **username_0**: Thank you for your link. It answers to the first part of my question, but doesn't answers wether there are problems which arent in co-C under many-one reduction and are in C under Turing reduction, for any C.  
> **username_2**: Sorry, this may seem an elementary question or maybe I am not thinking straight at this late hour but I am missing something in the wiki article. The article says that under Cook reductions, NP-complete is equal to co-NP-complete, but I don't see it. NP-hard is equal to co-NP-hard w.r.t Cook reductions, but NP-complete means being both *NP-hard* **AND** *NP*, and I don't see why (e.g.) TAUT would be in NP? I.e. TAUT is co-NP-hard under Cook reductions but that is not enough for being NP-complete.  
> **username_3**: @Monoid, you should reword your question to reflect this clarification then. As such the question is ambiguous  
> **username_3**: possible duplicate of [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_3**: voting to close as duplicate of http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc (see mashca's answer below)  
> **username_2**: @Lev: Thanks for the answer but why would TAUT (=UNSAT) be in NP? NP is not known to be closed under Cook (polytime Turing) reductions. The situation seems to be similar to computability theory, replace NP, co-NP, and Cook reduction with r.e., co-r.e., and Turing reductions, and we know that the arithmetical hierarchy provably does not collapse under Turing reductions so I don't see what is different in the NP setting?  
> **username_0**: @Suresh I had already looked at the other question but it didn't answered to mine. I've edited it to be more precise.  
> **username_4**: @Lev Reyzin: The choice of reductions does not affect the definition of the classes NP and coNP!  
> **username_5**: I stand corrected - Cook reductions aren't useful for showing a problem is in NP.  
> **username_4**: @Peter: Thank you for editing the question.  It makes much more sense now.  

---

## 4 answers

### Answer by username_11 on 2010-08-27. Score: 7 | Accepted answer

Have a look at this [this question](https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc) and especially [this answer](https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc/139#139) by Aaron Sterling. In short: "they are conjectured to be distinct notions."

> **Comments:**
> **username_0**: I know that if NP!=co-NP, they are distinct notions because Turing reduction collapses them, but could there be differences which wouldn't be collapses, for example a problem in NPI under many-one reduction and in NPC under Turing reduction ?  
> **username_4**: @Monoïd: NP≠coNP does not imply (at least in an obvious way) that the two notions of reductions are distinct.  I am afraid that you are confusing the class NP (which is defined independently of the choice of the notion of reductions) with the class of decision problems reducible to NP (which depends on the choice of the notion of reductions).  
> **username_4**: Oops, my previous comment was wrong.  If NP≠coNP, the two notions of reductions are obviously distinct (SAT is unconditionally Turing reducible to UNSAT, but SAT is many-one reducible to UNSAT if and only if NP=coNP).  

---

### Answer by username_6 on 2010-08-29. Score: 10

The ["Boolean Hierarchy" BP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bh) is a whole hierarchy of combinations of NP problems under Karp reductions which are all in P^NP.


---

### Answer by username_7 on 2010-11-26. Score: 9

As far as I can tell, this question really comprises two distinct questions, the first of which appears in the title and the second of which is given after the edit.

(1) Do many-one reductions and Turing reductions define the same set of NP-complete problems (i.e. problems that are both in NP and which SAT can be reduced to)? Whether NPC under Turing reductions is the same as NPC under many-one reductions was still an open problem seven years ago, and I don't believe it has been closed since. See [this survey](http://www.cs.iastate.edu/~pavan/papers/sigact.pdf) from the June 2003 ACM SIGACT News for details.

(2) What is the class of problems which SAT has a Turing reduction to, and vice versa? This is the class of NP-hard problems (under Turing reductions) which are in PNP. For more information on this, see Noam's answer.

> **Comments:**
> **username_8**: link does not work.  

---

### Answer by username_9 on 2010-08-28. Score: 8

This doesn't answer your question, but one could ask the same question for weaker reductions. For example, does the set of NP-complete problems change if we permit only log space reductions, or only AC0 reductions, or even NC0 reductions. A suprising fact is that all known NP-complete problems are complete even with NC0 reductions.

Reference: Agrawal, M., Allender, E., and Rudich, S. 1997 Reductions in Circuit Complexity: an Isomorphism Theorem and a Gap Theorem.

> **Comments:**
> **username_7**: Is this question about weaker reductions still open? If I have a problem which was NP complete under P/poly or BPP reductions, but apparently not under P reductions without assuming unproven number theoretic assumptions, is it worth making a note of?  
> **username_9**: @Peter: In the paper I've cited, it is left open if there is any problem that is NP-complete under polynomial time reductions which isn't NP-complete under AC^0 reductions. This question has been answered by [Reducing the complexity of reductions](http://www.springerlink.com/content/bbar426549dv33ut/). They show a problem that is NP-complete with ACC reductions but not AC^0 reductions. None of these papers seem to comment on problems that are NP-complete under reductions stronger than polynomial time, and how that relates to the possibility of being NP-complete under polytime reductions.  
> **username_10**: I assume you only mean natural NPC problems, otherwise the NPC solver can request a correct hash input  

---

