turing reducibility

one problem is reducible to another if a method for solving the second problem yields a method for solving the first.
[cite:;taken from @computability_rogers_1987 chapter 6 reducibilities]

$\text{[math]}$ is many-one reducible ( $\text{[math]}$ -reducible) to $\text{[math]}$ (written $\text{[math]}$ ) if there is a computable function $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ , i.e., $\text{[math]}$ iff $\text{[math]}$ .
$\text{[math]}$ is one-one reducible (1-reducible) to $\text{[math]}$ ( $\text{[math]}$ ) if $\text{[math]}$ by a 1:1 computable function.

[cite:;taken from @computability_soare_2016 definition 1.6.8]

let $\text{[math]}$ be sets. $\text{[math]}$ is many-one reducible to $\text{[math]}$ , written $\text{[math]}$ , if there is a computable function $\text{[math]}$ such that
$\text{[math]}$ that is, $\text{[math]}$ iff $\text{[math]}$ . (the word many-one simply refers to the fact that we do not require $\text{[math]}$ to be one-one.)
[cite:;taken from @computability_davis_1994 chapter 4.6 diagonalization and reducibility]

a reduction function has to be a total computable function.

if $\text{[math]}$ and $\text{[math]}$ is computable then $\text{[math]}$ is computable.
[cite:;taken from @computability_soare_2016 proposition 1.6.10]

suppose $\text{[math]}$ .

if $\text{[math]}$ is recursive, then $\text{[math]}$ is recursive.
if $\text{[math]}$ is r.e., then $\text{[math]}$ is r.e.

[cite:;taken from @computability_davis_1994 chapter 4.6 diagonalization and reducibility; theorem 6.2]

let $\text{[math]}$ . if $\text{[math]}$ is noncomputable, then $\text{[math]}$ is also noncomputable. if $\text{[math]}$ isnt computably enumerable then $\text{[math]}$ is also not computably enumerable.

$\text{[math]}$

consider the function
$\text{[math]}$ this function acts as a reduction from $\text{[math]}$ to $\text{[math]}$ . for every program number $\text{[math]}$ (i.e. $\text{[math]}$ is the encoding of a program $\text{[math]}$ ), the function $\text{[math]}$ returns the code of the following program $\text{[math]}$ :
$\text{[math]}$ $\text{[math]}$ ignores its inputs and runs the given program $\text{[math]}$ on $\text{[math]}$ .
the given reduction function $\text{[math]}$ is computable: we can write an algorithm that receives $\text{[math]}$ and returns the encoding of the program $\text{[math]}$ (the encoding function should be computable).
we have $\text{[math]}$ :
$\text{[math]}$ we have shown the reduction from $\text{[math]}$ , since $\text{[math]}$ isnt computably enumerable, we have that $\text{[math]}$ is also not computably enumerable.

if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .
[cite:;taken from @computability_davis_1994 chapter 6.4 diagonalization and reducibility; theorem 6.3]

if $\text{[math]}$ is $\text{[math]}$ -complete, $\text{[math]}$ is r.e. and $\text{[math]}$ , then $\text{[math]}$ is $\text{[math]}$ -complete.
[cite:;taken from @computability_davis_1994 chapter 6.4 diagonalization and reducibility; corollary 6.4]

if $\text{[math]}$ then $\text{[math]}$ .

the proof is trivial, assuming there is a reduction function for $\text{[math]}$ , the same reduction function can be used for the reduction $\text{[math]}$ .

can regard any classification problem (on finitely described objects) as a subset of our set of inputs $\text{[math]}$ . efficient reductions provide a natural partial order on such problems that captures their relative difficulty. note that reductions are a primary tool in computability and recursion theory, from which computational complexity developed. there, reductions were typically simply computable functions, whereas the focus of computational complexity is on efficiently computable ones. while we concentrate here on time efficiency, the field studies a great variety of other resources; limiting these in reductions is as fruitful as limiting them in algorithms. the following crucial definition is depicted in [cite:;in @computation_wigderson_2019 figure 7].

let $\text{[math]}$ be two classification problems. $\text{[math]}$ is an efficient reduction from $\text{[math]}$ to $\text{[math]}$ if $\text{[math]}$ and for every $\text{[math]}$ we have $\text{[math]}$ iff $\text{[math]}$ . in this case, we call $\text{[math]}$ an efficient reduction from $\text{[math]}$ to $\text{[math]}$ . we write $\text{[math]}$ if there is an efficient reduction from $\text{[math]}$ to $\text{[math]}$ .
[cite:;taken from @computation_wigderson_2019 definition 3.10 efficient reductions]

[cite:;taken from @computation_wigderson_2019 chapter 3.6 reductions]