Enumeration reducibility

In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete. E-reducibility is a form of positive reducibility, meaning that only positive information is processed. Positive information denotes the logic syntax for "and" ([math]\displaystyle{ \land, \And }[/math]) and "or" ([math]\displaystyle{ \lor,\| }[/math]). The syntax for negation, "not" ([math]\displaystyle{ \neg }[/math]) is not included or used.

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

Let sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] 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 [math]\displaystyle{ B }[/math] are supplied, in any order whatsoever as inputs, then the computation always eventually yields the set [math]\displaystyle{ A }[/math], in some order, as outputs. The order in which the members of [math]\displaystyle{ A }[/math] appear may vary as the order of inputs varies. (We permit repetitions in the listing of [math]\displaystyle{ B }[/math] and in the listing of [math]\displaystyle{ A }[/math].) If such a procedure exists we say that [math]\displaystyle{ A }[/math] is enumeration reducible to [math]\displaystyle{ B }[/math].

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". This result extends to e-reducibility as well. E-reducibility 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 [math]\displaystyle{ \omega }[/math] denote the set of natural numbers ([math]\displaystyle{ \mathbb{N} }[/math]) and [math]\displaystyle{ A,B... }[/math] denote subsets of [math]\displaystyle{ \omega }[/math]. Let lower case letters [math]\displaystyle{ n,x... }[/math] and [math]\displaystyle{ f,g... }[/math] represent numbers and functions from [math]\displaystyle{ \omega }[/math] to [math]\displaystyle{ \omega }[/math].

Rogers' informal definition

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

For any [math]\displaystyle{ A,B\subseteq \omega, A }[/math] is enumeration reducible to [math]\displaystyle{ B }[/math] if there is an effective procedure for getting an enumeration of [math]\displaystyle{ A }[/math] from any enumeration of [math]\displaystyle{ B }[/math]. Thus we write:

[math]\displaystyle{ A\leq_eB }[/math]

which is the standard notation of enumeration reducibility.

Precise definition

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

For any [math]\displaystyle{ A, B \subseteq\omega, A\leq_eB }[/math] if there exists a computably enumerable set [math]\displaystyle{ W }[/math] such that, for all [math]\displaystyle{ x\in\omega, }[/math]

[math]\displaystyle{ x\in A }[/math] [math]\displaystyle{ \Leftrightarrow }[/math] [math]\displaystyle{ \exists D[\langle x,D\rangle\in W }[/math] [math]\displaystyle{ \And }[/math] [math]\displaystyle{ D\subseteq B]. }[/math]

In this case, we write that

[math]\displaystyle{ A\leq_eB }[/math] via [math]\displaystyle{ W }[/math]

or that [math]\displaystyle{ W }[/math] (the enumeration operator) witnesses [math]\displaystyle{ A\leq_eB }[/math].

Properties

Equivalence

• If [math]\displaystyle{ A\leq_eB }[/math] and [math]\displaystyle{ B\leq_eA, }[/math] [math]\displaystyle{ A }[/math] is considered to be equivalent through enumeration to [math]\displaystyle{ B }[/math]. Thus we write

[math]\displaystyle{ A\equiv_eB. }[/math]

• Conversely, if [math]\displaystyle{ A\leq_eB }[/math] but [math]\displaystyle{ B\nleq_eA, }[/math] we write

[math]\displaystyle{ A\lt _eB. }[/math]

• Inversely, if [math]\displaystyle{ A\nleq_eB }[/math] and [math]\displaystyle{ B\nleq_eA, }[/math] we write

[math]\displaystyle{ A }[/math] [math]\displaystyle{ |_e }[/math] [math]\displaystyle{ B. }[/math]

Supremum

• The supremum (least upper bound, join) of sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] with respect to [math]\displaystyle{ \leq_e }[/math] is given by the disjoint union

[math]\displaystyle{ A\oplus B=\{2n:n\in A\}\cup\{2n+1:n\in B\}. }[/math]

Turing reduction

• A relationship between Turing reducibility, e-reducibility, and the relation "computably enumerable in" can be shown using the operation [math]\displaystyle{ A^+=A\oplus\overline{A} }[/math], which codes in a positive way the positive and negative information about [math]\displaystyle{ A }[/math]. It is stated as follows:

1. [math]\displaystyle{ A\leq_TB\iff A^+\leq_eB^+ }[/math]
2. [math]\displaystyle{ A }[/math] is computably enumerable in [math]\displaystyle{ B }[/math] if and only if [math]\displaystyle{ A\leq_eB^+ }[/math].

Variants

Strong enumeration reducibilities

In addition to e-reducibility, there exist strong versions, the most important one being s-reducibility (named after Robert M. Solovay). S-reducibility states that a computably enumerable real set [math]\displaystyle{ A }[/math] is s-reducible to another computably enumerable real set [math]\displaystyle{ B }[/math] if [math]\displaystyle{ B }[/math] is at least as difficult to be approximated as [math]\displaystyle{ A }[/math]. This method shows similarity to e-reducibility in that it compares the elements of multiple sets. In addition, the structure of s-degrees have natural analogs in the enumeration degrees.

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 [math]\displaystyle{ x\in A }[/math]?" is only given if [math]\displaystyle{ x\in A }[/math], and is not true for the inverse.) because they inherently model computational situations where incomplete oracle information is available. This is in contrast from the well-studied Turing reducibility, in which information is captured in both negative and positive values. In addition, T-reducibility uses information that is provided immediately and without delay. A strong reducibility is utilized in order to prevent problems occurring when incomplete information is supplied.

Partial functions

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

[math]\displaystyle{ f\leq_eg\Leftrightarrow }[/math] graph[math]\displaystyle{ (f)\leq_e }[/math] graph[math]\displaystyle{ (g). }[/math]

Kleene's recursion theorem introduces the notion of relative partial recursiveness, which, by means of systems of equations, can demonstrate equivalence through [math]\displaystyle{ \leq_e }[/math] between graphs of partial functions. E-reducibility relates to relative partial recursiveness in the same way that T-reducibility relates to μ-recursiveness.

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