Misplaced Pages

Enumeration reducibility

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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. 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". 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.

Definition

Source:

Let ( D u ) {\displaystyle (D_{u})} be a standard numbering of finite subsets of N {\displaystyle \mathbb {N} } , and let ⟨ ∙ , ∙ ⟩ {\displaystyle \langle \bullet ,\bullet \rangle } be a standard pairing function. A set A ⊆ N {\displaystyle A\subseteq \mathbb {N} } is enumeration reducible to a set B ⊆ N {\displaystyle B\subseteq \mathbb {N} } if there exists a computably enumerable set W {\displaystyle W} such that for all x ∈ N {\displaystyle x\in \mathbb {N} } ,

x ∈ A ⟺ ∃ u , ( D u ⊆ B ∧ ⟨ x , D ⟩ ∈ W ) {\displaystyle 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 ≤ e B {\displaystyle A\leq _{e}B} . The relation ≤ e {\displaystyle \leq _{e}} is a preorder. Its associated equivalence relation is denoted by ≡ e {\displaystyle \equiv _{e}} .

Properties

  • The supremum (least upper bound, join) of sets A {\displaystyle A} and B {\displaystyle B} with respect to ≤ e {\displaystyle \leq _{e}} is given by the disjoint union
A ⊕ B = { 2 n : n ∈ A } ∪ { 2 n + 1 : n ∈ B } . {\displaystyle A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}.}
  • A is Turing reducible to B if and only if A + {\displaystyle A^{+}} is enumeration reducible to B + {\displaystyle B^{+}} , where the plus operator is defined as A + := A ⊕ A ¯ {\displaystyle A^{+}:=A\oplus {\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 + {\displaystyle 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 {\displaystyle A} is s-reducible to another computably enumerable real set B {\displaystyle B} if B {\displaystyle B} is at least as difficult to be approximated as A {\displaystyle A} . 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 ∈ A {\displaystyle x\in A} ?" is only given if x ∈ A {\displaystyle 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 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 ) = { ⟨ x , y ⟩ {\displaystyle (f)=\{\langle x,y\rangle } | {\displaystyle |} f ( x ) = y } {\displaystyle f(x)=y\}} , etc., we can define for partial functions f , g {\displaystyle f,g} :

f ≤ e g ⇔ {\displaystyle f\leq _{e}g\Leftrightarrow } graph ( f ) ≤ e {\displaystyle (f)\leq _{e}} graph ( g ) . {\displaystyle (g).}

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

See also

References

  1. 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.
  2. 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.
  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. 25 (4): 362–363. doi:10.2307/2963569. ISSN 0022-4812. JSTOR 2963569. S2CID 124102995.
  4. Harris, Charles Milton (2006). Enumeration Reducibility and Polynomial Time. CiteSeerX 10.1.1.95.8166.
  5. 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.
  6. ^ 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
  7. 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.
  8. 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.
  9. 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.
  10. 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)

Further reading

Introduction to Metamathematics

"Theory of Recursive Functions and Effective Computability"

Enumeration Reducibility and Polynomial Time

Categories: