Enumeration reducibility explained

In computability theory, enumeration reducibility (or e-reducibility for short) is a specific type of reducibility. Roughly speaking, A is enumeration-reducible to B if an enumeration of B can be algorithmically converted to an enumeration of A. In particular, if B is computably enumerable, then A also is.

Introduction

In one of the possible formalizations of the concept, a Turing reduction from A to B is a Turing machine augmented with a special instruction "query the oracle". This instruction takes an integer x and instantly returns whether x belongs to B. The oracle machine should compute A, possibly using this special capability to decide B. Informally, the existence of a Turing reduction from A to B means that if it is possible to decide B, then this can be used to decide A.

Enumeration reducibility is a variant whose informal explanation is, instead, that if it is possible to enumerate B, then this can be used to enumerate A. The reduction can be defined by a Turing machine with a special oracle query instruction which takes no parameter, and either returns a new element of B, or returns no output. The oracle supplies the elements of B in any order. It can possibly return no output for some queries before resuming the enumeration. The machine should similarly the members of A, in any order and at any pace.^[1] Repetitions in the enumerations of A and B may be permitted or not; the concept is equivalent in both cases. Although this could be made precise, the definition given below is more common since it is formally simpler.

Enumeration reducibility is a form of positive reducibility, in the sense that the oracle machine receives information about which elements are in B (positive information), but no information about which elements are not in B (negative information). Indeed, if an element has not been listed yet, the oracle machine cannot know whether it will be listed later, or never.

The concept of enumeration 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".^[2] This result extends to enumeration reducibility as well. Enumeration 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.^[3]

Definition^[4]

Let

(D _{u)} be a standard numbering of finite subsets of N , and let \langle \bullet, \bullet \rangle be a standard pairing function. A set A \subseteq N is enumeration reducible to a set B \subseteq N if there exists a computably enumerable set W such that for all x \in N ,x \in A \iff \exists u, (D _{u} \subseteq B \land \langle x, D \rangle \in W)

When A is enumeration reducible to B, we write

A \leq _{e} B . The relation \leq _{e} is a preorder. Its associated equivalence relation is denoted by \equiv _{e} .^[5]

Properties

• The supremum (least upper bound, join) of sets

A and B with respect to \leq _{e} is given by the disjoint unionA ⊕ B = \{ 2 n:n\in A\}\cup\{ 2 n +1 :n\in B\}.

• A is Turing reducible to B if and only if

A ^{+} is enumeration reducible to B ^{+} , where the plus operator is defined as A ^{+} : = A ⊕ \overline{A} . Informally, this operator encodes the positive and negative information about A in a positive way. Likewise, A is computably enumerable with oracle B if and only if A is enumeration reducible to B ^{+} .

• Furthermore, A is enumeration reducible to B if and only if, for all X such that B is computably enumerable with oracle X, it holds that A is also computably enumerable with oracle X. This is Selman's theorem.

Variants

Strong enumeration reducibilities

In addition to enumeration 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

A is s-reducible to another computably enumerable real set B if B is at least as difficult to be approximated as A .^[6] 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

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.^[7] 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

(f) = \{\langle x,y\rangle | f(x) = y\} , etc., we can define for partial functions f,g :^[8] f\leq _{eg\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, can demonstrate equivalence through

\leq _{e} between graphs of partial functions.^[9] 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

References

1. Shoenfield. J. R.. July 1969. Theory of Recursive Functions and Effective Computability (Hartley Rogers, Jr.). SIAM Review. 11. 3. 415–416. 10.1137/1011079. 0036-1445.
2. Myhill. John. 1961. Note on degrees of partial functions. Proceedings of the American Mathematical Society. en. 12. 4. 519–521. 10.1090/S0002-9939-1961-0125794-X. 0002-9939. free.
3. Sacks. Gerald E.. December 1960. Richard M. Friedberg and Hartley RogersJr., Reducibility and completeness for sets of integers. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117–125.. The Journal of Symbolic Logic. en. 25. 4. 362–363. 10.2307/2963569. 2963569. 124102995 . 0022-4812.
4. Book: Harris, Charles Milton. Enumeration Reducibility and Polynomial Time. 2006. 10.1.1.95.8166.
5. Case. John. 1971-02-01. Enumeration reducibility and partial degrees. Annals of Mathematical Logic. en. 2. 4. 419–439. 10.1016/0003-4843(71)90003-9. 0003-4843.
6. Book: Zheng. Xizhong. Rettinger. Robert. Computing and Combinatorics . On the Extensions of Solovay-Reducibility . 2004. Chwa. Kyung-Yong. Munro. J. Ian J.. https://link.springer.com/chapter/10.1007%2F978-3-540-27798-9_39. Lecture Notes in Computer Science. 3106. en. Berlin, Heidelberg. Springer. 360–369. 10.1007/978-3-540-27798-9_39. 978-3-540-27798-9.
7. Omanadze. Roland Sh.. Sorbi. Andrea. 2006-10-01. Strong Enumeration Reducibilities. Archive for Mathematical Logic. en. 45. 7. 869–912. 10.1007/s00153-006-0012-4. 44764613. 1432-0665.
8. Book: Cooper, S. Barry. Recursion Theory Week . Enumeration reducibility, nondeterministic computations and relative computability of partial functions . 1990. Ambos-Spies. Klaus. Müller. Gert H.. Sacks. Gerald E.. https://link.springer.com/chapter/10.1007%2FBFb0086114. Lecture Notes in Mathematics. 1432. en. Berlin, Heidelberg. Springer. 57–110. 10.1007/BFb0086114. 978-3-540-47142-4.
9. Book: Kleene, Stephen Cole, 1909-1994.. Introduction to metamathematics.. 1971. Wolters-Noordhoff Pub. 0-7204-2103-9. Groningen. 768949.

Further reading

Introduction to Metamathematics

"Theory of Recursive Functions and Effective Computability"

Enumeration Reducibility and Polynomial Time