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

Question

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 complement $\overline{A}$ is decidable.
  • Show that $A$ is decidable.
• Show $A$ is unrecognizable
  • Show that $A$ and $\overline{A}$ are both undecidable.
  • Are there any other ways to show a language is unrecognizable?.
• Show $A$ is $C$-complete
  • Show $A \in C$, and for some known $C$-complete language $B$, give a reduction $B \leq_m A$.
    • The reduction $R$ must meet the following restriction: If the complexity class $C$ has upper bound $f(x)$ on resource $S$ for some positive quantity $x$ of abstract machines that decide languages in $C$, then $g(x)$ measures the $S$-complexity of $R$ such that $g(x) \in o(f(x))$.
    • I'm not entirely comfortable with this definition, because, well, $PSPACE$-complete reductions are only required to have polynomial running time. In this case, I think any polynomial-time algorithm has space-complexity asymptotically less than $PSPACE$.
    • This line of reasoning doesn't add up either, because it is not known that $P \subset PSPACE$ (help?).

In general, it seems anywhere a many-one reductions is used, a Turing reduction may be used, but I'm not sure if the opposite is true. This is where my question about undecidability comes in: Can a many-one reduction be used to show that a language is undecidable? If this were possible, what would it imply?

Answer 1

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.