Shore and Slaman's analysis of the polynomial-time Turing (p-T) degrees Rpt\mathbf{R}_{\mathrm{pt}} of the recursive (decidable) sets (IEEE SCT 1989; journal version 1992) proved that every recursively presented lattice embeds into Rpt\mathbf{R}_{\mathrm{pt}}, that the structure satisfies the extension-of-embeddings property, and hence that the two-quantifier (∀∃\forall\exists) theory of Rpt\mathbf{R}_{\mathrm{pt}} is decidable; alongside these results the authors raised follow-up open questions for the neighbouring reducibilities and the larger degree structures. The decidability of the two-quantifier theory of the polynomial-time many-one degrees Rpm\mathbf{R}_{\mathrm{pm}}, a question raised by Shore and Slaman, was resolved affirmatively by Ambos-Spies, Fejer, Lempp and Lerman (1996). Three strands remain open in the spirit of that program and are recorded here: (1) the bounded-query program for the polynomial-time nn-truth-table (p-n-tt) degrees of the recursive sets, namely which lattices embed, whether the extension-of-embeddings property holds, and whether the two-quantifier theories of these structures are decidable; (2) whether recursiveness is first-order definable in the full p-time degree structure of all sets; and (3) the analogy with truth-table and bounded truth-table degree structures, namely whether the first-order theories of the tt-degrees above 0′0' and of the p-T degrees of all sets differ and whether the polynomial-time and elementary-time degree structures are isomorphic. In this last direction Mytilinaios and Slaman (2003) proved that the truth-table degrees above 0′0' are not isomorphic to the polynomial-time degrees of all sets, stated their belief that the two structures have different first-order theories, and asked whether the polynomial-time and elementary-time degree structures are isomorphic.

Background

A set AA of binary strings is polynomial-time Turing reducible to BB, written A≤ptBA \leq_{\mathrm{pt}} B, if a deterministic oracle machine with oracle BB decides AA in time polynomial in the input length; AA and BB are p-T equivalent if each reduces to the other, and the equivalence classes are the p-T degrees. Rpt\mathbf{R}_{\mathrm{pt}} denotes the p-T degrees of recursive (decidable) sets, and the p-T degrees of arbitrary sets form the larger structure in which Rpt\mathbf{R}_{\mathrm{pt}} sits as an ideal (it is closed downward and under joins). Polynomial-time many-one reducibility (A≤pmBA \leq_{\mathrm{pm}} B if there is a polynomial-time computable ff with A(x)=B(f(x))A(x) = B(f(x))) is stricter and yields the many-one degrees Rpm\mathbf{R}_{\mathrm{pm}}; Rpm\mathbf{R}_{\mathrm{pm}} is a distributive upper semilattice (a partially ordered set in which any two elements have a least upper bound, the join of two degrees being given by an effective disjoint union of representatives, and in which the distributive law holds), so non-distributive lattices cannot embed into it as sublattices. Between p-m and p-T sit the bounded-query reducibilities: a truth-table (tt) reduction fixes its entire finite list of oracle queries before seeing any answers (nonadaptive computation), and a p-n-tt reduction is a polynomial-time tt reduction asking at most nn queries for fixed nn; a single-query tt reduction is like a many-one reduction except that a Boolean function of the answer may be applied, and as nn grows the reducibility strengthens towards p-T, so the induced degree structures coarsen towards the p-T degrees. Each of these reducibilities induces a degree structure that is an upper semilattice with least element 00. Two structural questions drive the area. The lattice-embedding question asks which recursively presented lattices, i.e. lattices whose domain is a recursive set and whose join and meet operations are given by recursive functions, occur as sublattices of a given degree structure. The extension-of-embeddings problem asks whether every finite partial structure already embedded can be further extended inside the structure to realize any prescribed finite extension. Shore and Lerman observed that for such degree structures a two-quantifier (∀∃\forall\exists) sentence in the partial-order language is true exactly when a finite extension-of-embeddings condition is satisfiable: the universal quantifiers distill into a finite universal diagram Θ\Theta and the existential part into finitely many existential diagrams Ψi\Psi_i, and the sentence holds iff every embedding of Θ\Theta extends to one realizing some Ψi\Psi_i. Deciding which finite extension instances are satisfiable therefore decides the two-quantifier theory. Historically, Ladner (1975) proved the p-T degrees of recursive sets are dense, introducing delayed diagonalization, a technique that meets diagonalization requirements against previously constructed sets while respecting a polynomial time bound by delaying each diagonalization step until it can be completed within the bound. Ambos-Spies (1985) embedded every countable distributive lattice into every interval of the p-m and p-T degrees of the recursive sets, and noted that the construction works for the common intermediate reducibilities as well. Shore and Slaman (1989, journal version 1992), combining the Pudlak-Tuma representation of finite lattices by partitions (every finite lattice embeds into a finite partition lattice) with a 'looking back' organization of priority constructions (stage-by-stage constructions in which finitely many requirements may be injured and later repaired), upgraded the embedding theorem to all recursively presented lattices, verified the full extension-of-embeddings property for Rpt\mathbf{R}_{\mathrm{pt}}, and concluded decidability of its two-quantifier theory, together with strong nonhomogeneity results. The full first-order theories are nonetheless undecidable: Shinoda and Slaman (1990) interpreted first-order arithmetic in the p-T degrees of the recursive sets and second-order arithmetic in the p-T degrees of all sets. On the classical recursion-theoretic side, the truth-table degrees of all sets, and the interval above the degree 0′0' of the halting problem, are the analogues of the polynomial-time structures; Mytilinaios and Slaman (2003), using specifying sequences (finite sequences of degrees that pin down an infinite sequence of degrees exactly, in the tradition of exact-pair arguments, where an exact pair for a countable ideal is a pair of degrees whose common lower cone is exactly that ideal), proved that the tt-degrees above 0′0' are not isomorphic to the p-T degrees of all sets, and posed the analogous question for the elementary-time degrees (sets decidable within a time bound given by a fixed tower of exponentials). Shore and Slaman settled the full extension-of-embeddings problem for Rpt\mathbf{R}_{\mathrm{pt}} and proved an extension-of-embeddings theorem for the p-m degrees of the recursive sets. Whether the Shore-Slaman lattice-embedding, extension-of-embeddings and two-quantifier machinery carries over to the classical truth-table and bounded truth-table degree structures, and what new obstacles arise there, is the general direction behind these questions.

Problem Statement

The source paper settled the lattice-embedding, extension-of-embeddings and two-quantifier-theory questions for the p-T degrees Rpt\mathbf{R}_{\mathrm{pt}} of the recursive sets and raised follow-up open problems for the neighbouring reducibilities and the larger structures. One of these, the decidability of the two-quantifier theory of the p-m degrees Rpm\mathbf{R}_{\mathrm{pm}} — a question of Shore and Slaman — has since been resolved affirmatively (in the language {≤,0}\{\leq, 0\}), and is therefore excluded from the open core. Six open questions survive; the bounded-query strand is split below into its three questions (1)–(3), the definability strand is question (4), and the truth-table-analogy strand is questions (5)–(6). For an integer n≥1n \geq 1, let Rp-n-tt\mathbf{R}_{\mathrm{p}\text{-}n\text{-}\mathrm{tt}} be the degrees of the recursive sets under polynomial-time truth-table reducibility with at most nn nonadaptive queries.

(1) Bounded-query lattice embeddings: which recursively presented lattices embed into Rp-n-tt\mathbf{R}_{\mathrm{p}\text{-}n\text{-}\mathrm{tt}} for each nn? The two ends of the reducibility spectrum differ (the p-m degrees are distributive, so non-distributive lattices such as the five-element modular lattice M5M_5 and the five-element non-modular lattice N5N_5 cannot embed there, while every recursively presented lattice embeds at the p-T end), and Ambos-Spies's embedding of every countable distributive lattice is the main positive fact known at the intermediate query bounds.

(2) Bounded-query extension of embeddings: does the extension-of-embeddings property hold for Rp-n-tt\mathbf{R}_{\mathrm{p}\text{-}n\text{-}\mathrm{tt}} for each nn?

(3) Bounded-query two-quantifier theory: is the two-quantifier (∀∃\forall\exists) theory of Rp-n-tt\mathbf{R}_{\mathrm{p}\text{-}n\text{-}\mathrm{tt}} decidable for each nn?

(4) Definability of recursiveness: is the class of p-T degrees of recursive sets first-order definable inside the full p-T degree structure of all sets, concretely, is there a first-order property in the language of the degree order that characterizes exactly the degrees containing recursive sets? Adjacent rigidity questions raised by the follow-up literature (whether the full structure, or Rpt\mathbf{R}_{\mathrm{pt}} itself, admits nontrivial automorphisms, and whether natural complexity-class ideals are definable in these structures) remain open as context.

(5) Truth-table first-order theories: do the first-order theories of the tt-degrees above 0′0' and of the p-T degrees of all sets differ (the belief stated by Mytilinaios and Slaman)?

(6) Polynomial-time versus elementary-time degrees: are the polynomial-time and elementary-time Turing degree structures isomorphic (Mytilinaios and Slaman, Question 3.1)?

References

  1. Richard A. Shore and Theodore A. Slaman, "The P-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two quantifier theory", in Proceedings of the Structure in Complexity Theory Fourth Annual Conference (IEEE SCT 1989), IEEE Computer Society Press, 1989, pp. 68-76. DOI: 10.1109/SCT.1989.41804, https://doi.org/10.1109/SCT.1989.41804
  2. Richard A. Shore and Theodore A. Slaman, "The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory", Theoretical Computer Science 97(2):263-284, 1992. DOI: 10.1016/0304-3975(92)90078-T, https://doi.org/10.1016/0304-3975(92)90078-T
  3. Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp and Manuel Lerman, "Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices", Journal of Symbolic Logic 61(3):880-905, 1996. DOI: 10.2307/2275790, https://doi.org/10.2307/2275790
  4. Klaus Ambos-Spies and André Nies, "The theory of the polynomial many-one degrees of recursive sets is undecidable", in STACS 92 (9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992), Lecture Notes in Computer Science 577, Springer, Berlin, 1992, pp. 209-218. DOI: 10.1007/3-540-55210-3_185, https://doi.org/10.1007/3-540-55210-3_185
  5. Juichi Shinoda and Theodore A. Slaman, "On the theory of the PTIME degrees of the recursive sets", Journal of Computer and System Sciences 41(3):321-366, 1990. DOI: 10.1016/0022-0000(90)90024-F, https://doi.org/10.1016/0022-0000(90)90024-F
  6. Michael E. Mytilinaios and Theodore A. Slaman, "Differences between Resource Bounded Degree Structures", Notre Dame Journal of Formal Logic 44(1):1-12, 2003. DOI: 10.1305/ndjfl/1082637612, https://doi.org/10.1305/ndjfl/1082637612
  7. Kunimasa Aoki, Juichi Shinoda and Teruko Tsuda, "On Π2\Pi_2 theories of hp-T degrees of low sets", Theoretical Computer Science 123(2):315-327, 1994. DOI: 10.1016/0304-3975(92)00077-5, https://doi.org/10.1016/0304-3975(92)00077-5
  8. Christine Haught and Theodore A. Slaman, "Automorphisms in the PTIME-Turing degrees of recursive sets", Annals of Pure and Applied Logic 84(1):139-152, 1997. DOI: 10.1016/S0168-0072(95)00065-8, https://doi.org/10.1016/S0168-0072(95)00065-8
  9. Juichi Shinoda, "Strong polynomial-time reducibility", Annals of Pure and Applied Logic 84(1):97-117, 1997. DOI: 10.1016/S0168-0072(96)00037-1, https://doi.org/10.1016/S0168-0072(96)00037-1
  10. Klaus Ambos-Spies, "Polynomial time reducibilities and degrees", in Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, Elsevier, 1999, pp. 683-705. DOI: 10.1016/S0049-237X(99)80034-2, https://doi.org/10.1016/S0049-237X(99)80034-2
  11. Klaus Ambos-Spies, "Sublattices of the polynomial time degrees", Information and Control 65(1):63-84, 1985. DOI: 10.1016/S0019-9958(85)80020-6, https://doi.org/10.1016/S0019-9958(85)80020-6
  12. Richard E. Ladner, "On the structure of polynomial time reducibility", Journal of the ACM 22(1):155-171, 1975. DOI: 10.1145/321864.321877, https://doi.org/10.1145/321864.321877