Enumeration reducibility

Last updated September 06, 2024

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.^{[ citation needed ]} 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

Source:^[4]

Let $(D_{u})$ be a standard numbering of finite subsets of $\mathbb {N}$ , and let $\langle \bullet ,\bullet \rangle$ be a standard pairing function. A set $A\subseteq \mathbb {N}$ is enumeration reducible to a set $B\subseteq \mathbb {N}$ if there exists a computably enumerable set $W$ such that for all $x\in \mathbb {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 union

A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}.

^[6]

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\oplus {\overline {A}}$ .^[6] 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$ .^[7] 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.^[6]

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.^[8] 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$ :^[9]

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, can demonstrate equivalence through $\leq _{e}$ between graphs of partial functions.^[10]E-reducibility relates to relative partial recursiveness in the same way that T-reducibility relates to μ-recursiveness.^[6]

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:

In computability theory and computational complexity theory, a many-one reduction is a reduction that converts instances of one decision problem to another decision problem using a computable function. The reduced instance is in the language $if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language, we can decide whether instances are in its language by applying the reduction and solving for . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as . This means that any algorithm that solves can also be used as part of a program that solves .$

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In mathematics and computer algebra, automatic differentiation, also called algorithmic differentiation, computational differentiation, is a set of techniques to evaluate the partial derivative of a function specified by a computer program.

In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

In computability theory, a Turing reduction from a decision problem $to a decision problem is an oracle machine that decides problem given an oracle for . It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems.$

In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects.

In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as Soare (1987) and Rogers (1987).

In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set. It is reminiscent of the Schröder-Bernstein theorem in set theory and has been called a constructive version of it.

In computability theory, many reducibility relations are studied. They are motivated by the question: given sets $and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to .$

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals $. An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke-Platek set theory. In what follows is considered to be fixed.$

In computability theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory.

In computability theory, the T predicate, first studied by mathematician Stephen Cole Kleene, is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic. Informally, the T predicate tells whether a particular computer program will halt when run with a particular input, and the corresponding U function is used to obtain the results of the computation if the program does halt. As with the s_mn theorem, the original notation used by Kleene has become standard terminology for the concept.

A Multitrack Turing machine is a specific type of multi-tape Turing machine.

In mathematics, a set of natural numbers is called a K-trivial set if its initial segments viewed as binary strings are easy to describe: the prefix-free Kolmogorov complexity is as low as possible, close to that of a computable set. Solovay proved in 1975 that a set can be K-trivial without being computable.

In computability theory, Selman's theorem is a theorem relating enumeration reducibility with enumerability relative to oracles. It is named after Alan Selman, who proved it as part of his PhD thesis in 1971.

References

↑ Shoenfield, J. R. (July 1969). "Theory of Recursive Functions and Effective Computability (Hartley Rogers, Jr.)". SIAM Review. 11 (3): 415–416. doi:10.1137/1011079. ISSN 0036-1445.
↑ Myhill, John (1961). "Note on degrees of partial functions". Proceedings of the American Mathematical Society. 12 (4): 519–521. doi: 10.1090/S0002-9939-1961-0125794-X . ISSN 0002-9939.
↑ 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. 25 (4): 362–363. doi:10.2307/2963569. ISSN 0022-4812. JSTOR 2963569. S2CID 124102995.
↑ Harris, Charles Milton (2006). Enumeration Reducibility and Polynomial Time. CiteSeerX 10.1.1.95.8166 .
↑ Case, John (1971-02-01). "Enumeration reducibility and partial degrees". Annals of Mathematical Logic. 2 (4): 419–439. doi:10.1016/0003-4843(71)90003-9. ISSN 0003-4843.
1 2 3 4 Soskova, Alexandra A.; Soskova, Mariya I. (2017), Day, Adam; Fellows, Michael; Greenberg, Noam; Khoussainov, Bakhadyr (eds.), "Enumeration Reducibility and Computable Structure Theory", Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 10010, Cham: Springer International Publishing, pp. 271–301, doi:10.1007/978-3-319-50062-1_19, ISBN 978-3-319-50062-1 , retrieved 2020-12-18
↑ Zheng, Xizhong; Rettinger, Robert (2004). "On the Extensions of Solovay-Reducibility". In Chwa, Kyung-Yong; Munro, J. Ian J. (eds.). Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 3106. Berlin, Heidelberg: Springer. pp. 360–369. doi:10.1007/978-3-540-27798-9_39. ISBN 978-3-540-27798-9.
↑ Omanadze, Roland Sh.; Sorbi, Andrea (2006-10-01). "Strong Enumeration Reducibilities". Archive for Mathematical Logic. 45 (7): 869–912. doi:10.1007/s00153-006-0012-4. ISSN 1432-0665. S2CID 44764613.
↑ Cooper, S. Barry (1990). "Enumeration reducibility, nondeterministic computations and relative computability of partial functions". In Ambos-Spies, Klaus; Müller, Gert H.; Sacks, Gerald E. (eds.). Recursion Theory Week. Lecture Notes in Mathematics. Vol. 1432. Berlin, Heidelberg: Springer. pp. 57–110. doi:10.1007/BFb0086114. ISBN 978-3-540-47142-4.
↑ Kleene, Stephen Cole, 1909-1994. (1971). Introduction to metamathematics. Groningen: Wolters-Noordhoff Pub. ISBN 0-7204-2103-9. OCLC 768949.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)