<p>I don't know whether there is a preference, but they are conjectured to be distinct notions.  That is, Turing reducibility is conjectured to be a stronger notion.  (There exist A and B such that A is T-reducible to B, but not m-o reducible to B.)  One paper that discusses this is <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.465">this one</a> by Lutz and Mayordomo.  They propose a strengthening of the statement P != NP; roughly, that NP includes a non-negligible amount of EXPTIME.  This assumption allows them to show that the two notions of reducibility are distinct.</p>

CC BY-SA 2.5
2010-08-17T13:08:08.303Z
2010-08-17T13:08:08.303Z
Aaron Sterling
<p>I think the reason people prefer (to start with) many-one reductions is pedagogical -- a many-one reduction from A to B is actually a function on strings, whereas a Turing reduction requires the introduction of oracles.</p>

<p>Note that Cook reduction (polynomial-time Turing) and Karp-Levin reduction (polynomial-time many-one) are known to be distinct on E unconditionally, by Ko and Moore, and separately by Watanabe (as referenced in the Lutz and Mayordomo paper in Aaron Sterling's response).</p>

CC BY-SA 2.5
2010-08-17T13:37:31.060Z
2010-08-17T13:37:31.060Z
Joshua Grochow
<p>Turing reductions are more powerful than many-one mapping reductions in this regard: Turing reductions let you map a language to its complement.  As a result it can kind of obscure the difference between (for example) NP and coNP.  In Cook's original paper he didn't look at this distinction (iirc Cook actually used DNF formulas instead of CNF), but it probably became clear very quickly that this was an important separation, and many-one reductions made it easier to deal with this.</p>

CC BY-SA 2.5
2010-08-18T00:44:38.763Z
Stephen Cook pointed out during his keynote at FLoC 2010 that his 1971 paper actually claims to prove that SAT is complete for P^NP under Turing reductions...  Of course, the usual formulation follows from the same proof, so this is a situation of someone claiming less than they proved!  See http://4mhz.de/cook.html for a re-typeset version of the paper.  Also, the sentence "We have not been able to add either {primes} or {isomorphic graphpairs} to [the list of 4 NP-complete problems]" always makes me smile!
András Salamon
CC BY-SA 2.5
2010-08-17T15:07:50.967Z
2010-08-17T15:07:50.967Z
Kurt
<p>to jump off somewhat on other angle/ answer here by AS, this is an <a href="https://cstheory.stackexchange.com/a/18922/7884">open question</a> (also <a href="https://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc">here</a>) at the frontiers of TCS whether Cook ("Turing") reductions are different than Karp-Levin ("many-one") reductions, possibly equivalent to (major? key?) open questions of complexity class separations. here is a new result along these lines</p>

<p><a href="http://eccc.hpi-web.de/report/2014/126/" rel="nofollow noreferrer">Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis</a> / Debasis Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)</p>

<blockquote>
  <p>We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a <em>worst case</em> hardness hypothesis.</p>
</blockquote>

CC BY-SA 3.0
2014-10-10T16:02:58.323Z
2014-10-10T16:02:58.323Z
2017-04-13T12:32:28.080Z
vzn
<p>The definitions of efficient reducibility are motivated in part by an analogy with recursion theory. In recursion theory, the m-reductions are closely connected to the arithmetical hierarchy. (m-reductions preserve arithmetical degree). Arithmetical classifications are important beyond mere computability. For example, one can say that true $\Sigma_1$ statements are provable in Robinson's $Q$.</p>

<p>In complexity theory, there is also a notion of "polynomial hierarchy", though unlike the arithmetical hierarchy it is only conjectured to exist. This leads to classifications that are more subtle than "Is this problem as hard to solve as NP?"</p>

CC BY-SA 3.0
2011-11-23T12:23:30.173Z
2011-11-23T12:23:30.173Z
David Harris
<p>Generally, Many-one (Karp) reduction is easier to design because it is a restricted form of reduction that makes one call and the main task involves transforming the input into different encoding. Turing reduction may involve complex logic. Existence of a set that is complete for NP under Turing reduction but not under many-one reduction implies that P!=NP.</p>

<p>For instance, Unsatisfiability is complete for NP under Cook reduction but it is not known to be complete for NP under Karp reduction. So, if you prove that there is no Karp reduction from SAT to UNSAT (eqivalently from UNSAT to SAT) then you would prove that NP != CoNP and hence P!=NP.</p>

CC BY-SA 3.0
2011-11-23T02:20:56.173Z
can you give a reference to your last sentence or explain it?
Tayfun Pay
CC BY-SA 3.0
2011-11-23T11:54:35.783Z
I explained my last sentence.
Mohammad Al-Turkistany
CC BY-SA 3.0
2010-08-25T14:32:54.790Z
2011-11-23T11:53:48.377Z
2011-11-23T11:53:48.377Z
Mohammad Al-Turkistany
<p>Two reasons: </p>

<p>(1) just a matter of minimality: being NPC under many-one reductions is a formally stronger statement and if you get the stronger statement (as Karp did and as you almost always do) then why not say so?  </p>

<p>(2) Talking about many-one reductions gives rise to a richer, more delicate, hierarchy.  For example the distinction NP vs co-NP disappears under Turing reductions.</p>

<p>This is similar in spirit to why often one uses Logspace-reductions rather than polytime ones.</p>

CC BY-SA 2.5
2010-08-18T14:54:51.550Z
While (2) is certainly true, I can use (1) to argue that we should use one-one reductions.  Since most many-one reductions we build are in fact one-one reductions, why don't we study those when they are formally stronger and we get them most of the time anyways?  I think because it's simpler not to have to bother proving injectivity, even though we usually have it.  In that sense, maybe many-one reductions are sort of the "Goldilocks reductions" -- just the right power, just the right simplicity of proof.
Joshua Grochow
CC BY-SA 2.5
2010-08-17T17:00:38.473Z
2010-08-17T17:00:38.473Z
Noam
<p>Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?</p>

<cc.complexity-theory><np-hardness><reductions>
Many-one reductions vs. Turing reductions to define NPC
Matthias
# Many-one reductions vs. Turing reductions to define NPC

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

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?

**Tags:** cc.complexity-theory, np-hardness, reductions

---

## 7 answers

### Answer by username_9 on 2010-08-17. Score: 38 | Accepted answer

Two reasons:

(1) just a matter of minimality: being NPC under many-one reductions is a formally stronger statement and if you get the stronger statement (as Karp did and as you almost always do) then why not say so?

(2) Talking about many-one reductions gives rise to a richer, more delicate, hierarchy. For example the distinction NP vs co-NP disappears under Turing reductions.

This is similar in spirit to why often one uses Logspace-reductions rather than polytime ones.

> **Comments:**
> **username_2**: While (2) is certainly true, I can use (1) to argue that we should use one-one reductions.  Since most many-one reductions we build are in fact one-one reductions, why don't we study those when they are formally stronger and we get them most of the time anyways?  I think because it's simpler not to have to bother proving injectivity, even though we usually have it.  In that sense, maybe many-one reductions are sort of the "Goldilocks reductions" -- just the right power, just the right simplicity of proof.  

---

### Answer by username_1 on 2010-08-17. Score: 21

I don't know whether there is a preference, but they are conjectured to be distinct notions. That is, Turing reducibility is conjectured to be a stronger notion. (There exist A and B such that A is T-reducible to B, but not m-o reducible to B.) One paper that discusses this is [this one](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.465) by Lutz and Mayordomo. They propose a strengthening of the statement P != NP; roughly, that NP includes a non-negligible amount of EXPTIME. This assumption allows them to show that the two notions of reducibility are distinct.


---

### Answer by username_2 on 2010-08-17. Score: 18

I think the reason people prefer (to start with) many-one reductions is pedagogical -- a many-one reduction from A to B is actually a function on strings, whereas a Turing reduction requires the introduction of oracles.

Note that Cook reduction (polynomial-time Turing) and Karp-Levin reduction (polynomial-time many-one) are known to be distinct on E unconditionally, by Ko and Moore, and separately by Watanabe (as referenced in the Lutz and Mayordomo paper in Aaron Sterling's response).


---

### Answer by username_3 on 2010-08-17. Score: 7

Turing reductions are more powerful than many-one mapping reductions in this regard: Turing reductions let you map a language to its complement. As a result it can kind of obscure the difference between (for example) NP and coNP. In Cook's original paper he didn't look at this distinction (iirc Cook actually used DNF formulas instead of CNF), but it probably became clear very quickly that this was an important separation, and many-one reductions made it easier to deal with this.

> **Comments:**
> **username_4**: Stephen Cook pointed out during his keynote at FLoC 2010 that his 1971 paper actually claims to prove that SAT is complete for P^NP under Turing reductions...  Of course, the usual formulation follows from the same proof, so this is a situation of someone claiming less than they proved!  See http://4mhz.de/cook.html for a re-typeset version of the paper.  Also, the sentence "We have not been able to add either {primes} or {isomorphic graphpairs} to [the list of 4 NP-complete problems]" always makes me smile!  

---

### Answer by username_5 on 2014-10-10. Score: 5

to jump off somewhat on other angle/ answer here by AS, this is an [open question](https://cstheory.stackexchange.com/a/18922/7884) (also [here](https://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc)) at the frontiers of TCS whether Cook ("Turing") reductions are different than Karp-Levin ("many-one") reductions, possibly equivalent to (major? key?) open questions of complexity class separations. here is a new result along these lines

[Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis](http://eccc.hpi-web.de/report/2014/126/) / Debasis Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)

> We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a *worst case* hardness hypothesis.


---

### Answer by username_6 on 2011-11-23. Score: 4

The definitions of efficient reducibility are motivated in part by an analogy with recursion theory. In recursion theory, the m-reductions are closely connected to the arithmetical hierarchy. (m-reductions preserve arithmetical degree). Arithmetical classifications are important beyond mere computability. For example, one can say that true $\Sigma\_1$ statements are provable in Robinson's $Q$.

In complexity theory, there is also a notion of "polynomial hierarchy", though unlike the arithmetical hierarchy it is only conjectured to exist. This leads to classifications that are more subtle than "Is this problem as hard to solve as NP?"


---

### Answer by username_7 on 2010-08-25. Score: 3

Generally, Many-one (Karp) reduction is easier to design because it is a restricted form of reduction that makes one call and the main task involves transforming the input into different encoding. Turing reduction may involve complex logic. Existence of a set that is complete for NP under Turing reduction but not under many-one reduction implies that P!=NP.

For instance, Unsatisfiability is complete for NP under Cook reduction but it is not known to be complete for NP under Karp reduction. So, if you prove that there is no Karp reduction from SAT to UNSAT (eqivalently from UNSAT to SAT) then you would prove that NP != CoNP and hence P!=NP.

> **Comments:**
> **username_8**: can you give a reference to your last sentence or explain it?  
> **username_7**: I explained my last sentence.  

---

