What is the difference between turing reductions and many-one reductions?

To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is $C$-complete and the complexity of the reduction is asymptotically less than the upper bound of the complexity class (I just made this up, but it seems to be the case for the reduction to be at all useful; can someone verify?). Restrictions with respect to resource usage make sense to me: Why would anyone need to reduce a problem $B$ to some other problem $A$ if the computation of the reduction is greater than or equal to the computation of $B$?

However, I am taught that such reductions (showing that something is $C$-complete) must be of the many-one kind. Assume we are only talking about decision problems. Why does it matter how the reduction is done, as long as it proves whatever we are trying to prove (i.e. $A$ is $C$-Complete)?

Below are some statements I've established from my studies. Some are incomplete (I have not proven all of them), but my intuition tells me that all of these statements ought to be true. Can someone please confirm/correct my statements below?

• Show A is decidable

• Construct a decider $M'$ of $A$ using a machine $M$ for decidable language $B$. This reduction does not turn instances of $A$ into instances of $B$, but it still decides $A$, so we say this is a Turing reduction from $A$ to $B$.

• Give a many-one reduction from $A$ to $B$. This will show that $A$ is decidable, albeit overkill.

• Show A is undecidable

• For some known undecidable language $B$, Give a Turing reduction from $A$ to $B$.

• For some known undecidable language $B$, Give a many-one reduction from $A$ to $B$ (is this impossible?).

• Show A is recognizable

• For some recongizable language $B$, give a reduction from $A$ to $B$.

• Give a T.M. $M$ that accepts strings in the language of $A$; $M$ is not required to reject strings not in $A$ (it may never halt).

• Show its co

You got it backwards. Turing reductions are more general than many-one reduction. A many-one reduction is also a Turing reduction, but some Turing reductions are not many-one reductions. This is provably the case for (arbitrary) computable reductions. For example, there is a Turing reduction from the halting problem to its complement, but no such many-one reduction.

Completeness is defined with respect to many-one reductions since it allows making finer distinctions. Turing reductions, for example, don't allow us to distinguish the halting problem from its complement, or NP from coNP, but many-one reductions do.

StackExchange Computer Science Q#24580, answer score: 7