What are some non-trivial (please exclude poly time definitional difference) differences between Turing versus Many-one reductions in computability theory and those that occur in complexity theory?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Could you clarify your question? Of course there are big differences between Turing reduction and many-one reductions in computability theory, but you seem to ask not about those differences but about differences between those (different) things and some reductions (which ones?) in complexity theory? $\endgroup$– Joel David HamkinsCommented May 7, 2016 at 11:11
-
$\begingroup$ @JoelDavidHamkins for complexity theory using similar terminology en.wikipedia.org/wiki/Polynomial-time_reduction. It is an open problem if they are distinct in complexity theory unlike in computability theory? The essential diff in many-one reduction in complexity theory is total computable function $f$ is replaced by polynomial function. So wondering why is it open problem in complexity theory as against in computability theory? $\endgroup$– TurboCommented May 7, 2016 at 11:12
-
$\begingroup$ @JoelDavidHamkins Is there any possibility of something interesting in my post? $\endgroup$– TurboCommented May 7, 2016 at 11:36
-
2$\begingroup$ I think there is a deep question in this vicinity (and I wasn't the down-voter). There is an analogy between the reduction concepts of computability theory, which have been very successful and which have led to a clarifying theory with many results, and the reduction concepts of complexity theory, which is a theory where so many interesting questions, it seems, are still open. The deep question concerns the high-level explanation, if any, for this disanalogous situation in the results, when the basic analogy seems sound. $\endgroup$– Joel David HamkinsCommented May 7, 2016 at 11:42
-
$\begingroup$ @JoelDavidHamkins also is my observation right? Turing reductions have been proven distinct from many-one reductions in computability theory correct? $\endgroup$– TurboCommented May 7, 2016 at 11:43
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
12
The basic reductions in computability theory are:
- A set $A$ is Turing reducible to $B$, if there is a computable procedure that can correctly answer queries about $A$ using an oracle for $B$.
- A set $A$ is many-one reducible to $B$, if there is a computable function $f$ such that $n\in A\iff f(n)\in B$.
These reduction concepts differ in that Turing reducibility can make many calls to the oracle, and it can use that information either positively or negatively, but with many-one reducibility, you get just one call to the oracle, and you have to use that particular answer as the answer to your query.
In complexity theory, we make similar definitions, except insist that the computable procedures are polynomial time.
It is easy to see that Turing reducibility, in computability theory, is not the same as many-one reducibility. Here are two arguments:
A computable set is Turing reducible to any set at all, since you don't need the oracle, but a nonempty computable set cannot be reduced to the empty set, since $f(n)\in B$ is always false if $B$ is empty. Thus, to be specific, $\mathbb{N}$ is Turing reducible to $\emptyset$, but not many-one reducible.
Every set is Turing reducible to its complement, but if a set $A$ is many-one reducible to $B$ and $B$ is c.e., then $A$ will also be c.e. Therefore, the complement of the halting problem cannot many-one reduce to its complement, since it is not c.e.
Both of these argument also work in the context of complexity theory to show that polynomial time Turing reducibility is different than polynomial time many-one reducibility.
Namely, no nonempty decision problem is polynomial time many-one reducible to the empty set, but any polynomial time decidable problem is polynomial time Turing reducible to any set.
And secondly, the complement of the halting problem is easily polynomial time Turing reducible to its complement, but it is not polynomial time many-one reducible, since it is not many-one reducible by any computable function as I argued above. (Thanks to Emil for his comment.)
So the situation is that we may distinguish the two reducibility relations in complexity theory for essentially the same reasons that we may distinguish them in computability theory.
answered May 7, 2016 at 12:18
-
1$\begingroup$ The second argument also works unconditionally for poly-time reducibility: the halting problem is not poly-time many-one reducible to its complement. And unlike unrestricted reductions, one can also find nontrivial computable sets that are not poly-time many-one reducible to their complements (IIRC in EXP). $\endgroup$ Commented May 7, 2016 at 13:20
-
3$\begingroup$ @Turbo I don't understand your remark. The argument I give here, which I think is very well-known, does distinguish the relations. $\endgroup$ Commented May 7, 2016 at 13:59
-
2$\begingroup$ Yes. That is what I prove in my answer. The proof of this is no different in complexity theory than it is in computability theory. $\endgroup$ Commented May 8, 2016 at 3:46
-
2$\begingroup$ Did you read my answer? $\mathbb{N}$ is polynomial time Turing reducible to $\emptyset$, but not polynomial many-one reducible. $\endgroup$ Commented May 8, 2016 at 4:03
-
2$\begingroup$ Yes, my example shows that the two reducibility relations are definitely not the same relation. But since this argument is very easy and well understood, of course it is not solving any open question. Probably there is another open question concerning these reducibilities, which you are imperfectly recalling. For example, perhaps it isn't known whether they are the same in a certain restricted context? $\endgroup$ Commented May 8, 2016 at 12:18