The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory
Richard A. Shore, Theodore A. Slaman · Theoretical Computer Science · 1992
Ambos-Spies (1984a) showed that the two basic nondistributive lattices can be embedded in Rp-T, the polynomial-time Turing degrees of the recursive sets. We introduce more general techniques to extend his results to show that every recursive lattice can be embedded in Rp-T. In addition to lattice-theoretic representation theorems, we use the scheme of priority style arguments coupled with “looking back” techniques presented in Shinoda and Slaman (1988, 1990). We also generalize the density type results of Ladner (1975) and many others to settle the full extension of the embedding problem for Rp-T. Combined with the logical analysis of sentences with one alternation of quantifiers (Shore 1978, Lerman 1983), these results suffice to decide the full ∀∃-theory of Rp-T. They also give a strong nonhomogeneity result: the p-time degrees of the sets recursive in (and, if desired, p-time above) two distinct sets A and B are almost never isomorphic. The situation for the p-time many-one degrees is quite different. We decide the extension of the embedding problem (differently than for Rp-T) but not the ∀∃-theory.