Enumeration reducibility

In computablity theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for deteremining enumerability between sets of natural numbers.

E-reducibility is a form of positive reducibility, meaning that only positive information is processed. Only the syntax for "and" ($\land ,\And$) or "or" ($\lor ,\|$) is used. The logical syntax for negation, "not" ($\neg$) is not included.

According to Hartley Rogers Jr., an intuitive model that can be used to explain e-reducibility is as follows:

Let sets $A$ and $B$ be given. Consider a procedure that is determined by a finite set of instructions in the following way. A computation is begun. The computation proceeds algorithmically except that, from time to time, the computing agent may be requested to obtain an “input" integer, and, from time to time the procedure yields an “output” integer. When an input is requested, any integer, or no integer, may be supplied. Assume that when the members of $B$ are supplied, in any order whatsoever as inputs, then the computation always eventually yields the set $A$, in some order, as outputs. The order in which the members of $A$ appear may vary as the order of inputs varies. (We permit repetitions in the listing of $B$ and in the listing of $A$.) If such a procedure exists we say that $A$ is enumeration reducible to $B$.

The concept of e-reducibility was first introduced by the results of John Myhill, which concluded that "a set is many-one complete if and only if it is recursively enumerable and its complement is productive". The concept was later formally codified by Rogers and his collaborator Richard M. Friedberg in Zeitschrift für mathematische Logik und Grundlagen der Mathematik (the predecessor of Mathematical Logic Quarterly) in 1959.

Definitions

In the definitions provided below, let $\omega$ denote the set of natural numbers ($\mathbb {N}$) and $A,B...$ denote subsets of $\omega$. Let lower case letters $n,x...$ and $f,g...$ represent numbers and functions from $\omega$ to $\omega$.

Rogers' informal definition

In addition to his intuitive model, Rogers also provided a concise reformulation to create an informal definition. It reads:

For any $A,B\subseteq \omega ,A$ is enumeration reducible to $B$ if there is an effective procedure for getting an enumeration of $A$ from any enumeration of $B$. Thus we write:

$A\leq _{e}B$

which is the standard notation of enumeration reducibility.

Precise definition

From Rogers' informal definition, a precise definition can be inferred.

For any $A,B\subseteq \omega ,A\leq _{e}B$ if there exists a computably enumerable set $W$ such that, for all $x\in \omega ,$

$x\in A$ $\Leftrightarrow$ $\exists D[\langle x,D\rangle \in W$ $\And$ $D\subseteq B].$

In this case, we write that

$A\leq _{e}B$ via $W$

or that $W$ witnesses $A\leq _{e}B$.

Equivalence

If $A\leq _{e}B$ and $B\leq _{e}A,$ $A$ is considered to be equivalent through enumeration to $B$. Thus we write

$A\equiv _{e}B.$

Conversely, if $A\leq _{e}B$ but $B\nleq _{e}A,$ we write

$A<_{e}B.$

Inversely, if $A\nleq _{e}B$ and $B\nleq _{e}A,$ we write

$A$ $|_{e}$ $B.$

Applications

Strong enumeration reducibility

In addition to the e-reducibility, there exist strong versions, the most important one being s-reducibility (named after Robert M. Solovay). The reasoning for using s-reducibility is summarized by Omandaze and Sorbi as a result of positive reducibility models being unable to answer certain oracle questions (e.g. an answer to "Is $x\in A$?" is only given if $x\in A$, and is not true for the inverse.) because they inherently model computational situations where incomplete oracle information is available. This is in contrast from Turing reducibility, in which information is provided on demand and without any delay in time.

Partial functions

E-reducibility can be defined for partial functions as well. Writing graph$(f)=\{\langle x,y\rangle$ $|$ $f(x)=y\}$ , etc., we can define for partial functions $f,g$:

$f\leq _{e}g\Leftrightarrow$ graph$(f)\leq _{e}$ graph$(g).$

Kleene's recursion theorem introduces the notion of relative partial recursiveness, which, by means of systems of equations, is equavalent to $\leq _{e}$ between graphs of partial functions.

See also

Turing reduction

Many-one reduction

Truth-table reduction

Arithmetical hierarchy

Further reading

Introduction to Metamathematics

"Theory of Recursive Functions and Effective Computability"

Enumeration Reducibility and Polynomial Time