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?



Turing and Many one reductions in computability versus complexity
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. 


