What is the difference between Turing-reducibility and m-reducibility?

1.1k Views Asked by At

The set $A$ is many-one reducible (m-reducible) to the set $ B $ if there is a total computable function $f$ such that $x ∈ A $ iff $f(x) ∈ B$ for all $x$.

We shall write $A ≤_{m} B$

Let be $A, B \subset \mathbb{N}$

is it true that $A \leq_{m} B \implies A\leq_{T}B$?

Where $A\leq_{T}B$ is that $A$ is Turing-reducible to the set B.

If it is true, why do the mathematicians use more Turing-reducibility than m-reducibility? Can you give me some counterexample of two sets $A,B\subset \mathbb{N}$ where $A\leq_{T}B$ and $\neg (A\leq_{m}B)$?

1

There are 1 best solutions below

4
On BEST ANSWER

It is true that $\le_m$ implies $\le_T$. The converse, however, is false, so they are truly different things.

An easy example of this is supplied by the following: any set is Turing equivalent to its complement, but in general a set need not be many-one reducible to its complement. For example, if $C$ is a non-recursive recursively enumerable set, then $C$ is not many-one reducible to its complement.

This helps motivate $\le_T$ as opposed to $\le_m$: intuitively, a set has exactly as much information as its complement, just "twisted around" (in a very computable way); $\le_T$ reflects this but $\le_m$ doesn't. (That said, there are also situations where $\le_m$ is more natural.)


Incidentally, it's worth noting that there are other reducibilities strictly between $\le_m$ and $\le_T$, such as truth-table reducibility $\le_{tt}$ (with respect to which a set is equivalent to its complement).