6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is known that $P \subseteq PSPACE$. A Turing machine running in polynomial time uses up polynomial space. $\endgroup$ – Yuval Filmus May 11 '14 at 0:12
  • 1
    $\begingroup$ There are several other questions on this side addressing these issues. $\endgroup$ – Yuval Filmus May 11 '14 at 0:15
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Plese don't say "provably" unless you mean it :-) $\endgroup$ – Andrej Bauer May 12 '14 at 6:24
  • $\begingroup$ As always, thank you for the explanation Yuval. I think the conclusion I drew conveyed that Turing reductions are more general than many-one reductions. If I give you a Turing reduction that does show completeness for a particular language, then would such a reduction necessarily satisfy properties of a many-one reduction (i.e. it is a many-one reduction)? In particular, I am curious whether it is necessary to translate instances of one problem into another in order to show completeness via a reduction. This seems like it ought to be the case, but I would not know where to begin to prove it. $\endgroup$ – baffld May 13 '14 at 15:38
  • $\begingroup$ A Turing reduction from $A$ to $B$ need not be a many-one reduction, but the converse is true: a many-one reduction is a special case of Turing reductions. In the answer I give an example where there is a Turing reduction from $A$ to $B$ but no many-one reduction from $A$ to $B$. $\endgroup$ – Yuval Filmus May 13 '14 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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