43
$\begingroup$

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

$\endgroup$

7 Answers 7

38
$\begingroup$

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.

$\endgroup$
1
  • 19
    $\begingroup$ 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. $\endgroup$ Aug 18, 2010 at 14:54
21
$\begingroup$

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

$\endgroup$
0
18
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
  • 12
    $\begingroup$ 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 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! $\endgroup$ Aug 18, 2010 at 0:44
5
$\begingroup$

to jump off somewhat on other angle/ answer here by AS, this is an open question (also here) 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 / 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.

$\endgroup$
4
$\begingroup$

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?"

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ can you give a reference to your last sentence or explain it? $\endgroup$
    – Tayfun Pay
    Nov 23, 2011 at 2:20
  • 3
    $\begingroup$ I explained my last sentence. $\endgroup$ Nov 23, 2011 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.