\n Contains fulltext :\n 239187.pdf (Publisher’s version ) (Open Access)\n

Abstract We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.

Klaus Ambos-Spies, Arnold Beckmann, Erzsébet Csuhaj-Varjú, Benedikt Löwe; Computability in Europe 2009, Journal of Logic and Computation, Volume 23, Issue

We show that, for any abstract complexity measure in the sense of Blum and for any computable function f (or computable operator F), the class of problems that are f-speedable (or F-speedable) does not have effective measure 0. On the other hand, for sufficiently fast growing f (or F), the class of non-speedable computable problems does not have effective measure 0. These results answer some questions raised by Calude and Zimand. We also give a quantitative analysis of Borodin and Trakhtenbrot's Gap Theorem, which corrects a claim by Calude and Zimand.

Abstract We prove that every Turing degree a bounding some non-GL2 degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

Abstract. In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).

In this paper we investigate effective versions of Hausdorff dimension which have been recently introduced by Lutz. We focus on dimension in the class E of sets computable in linear exponential time. We determine the dimension of various classes related to fundamental structural properties including different types of autoreducibility and immunity. By a new general invariance theorem for resource-bounded dimension we show that the class of p-m-complete sets for E has dimension 1 in E. Moreover, we show that there are p-m-lower spans in E of dimension /spl Hscr/(/spl beta/) for any rational /spl beta/ between 0 and 1, where /spl Hscr/(/spl beta/) is the binary entropy function. This leads to a new general completeness notion for E that properly extends Lutz's concept of weak completeness. Finally we characterize resource-bounded dimension in terms of martingales with restricted betting ratios and in terms of prediction functions.

J.H. Lutz (1993) proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure. J.H. Lutz and E. Mayordomo (1996) showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ and they conjectured that further NP-completeness notions can be separated. Here we prove this conjecture for the bounded-query reducibilities. In fact we consider a new weaker hypothesis, namely the assumption that NP is not p-meager with respect to the resource bounded Baire category concept of Ambos-Spies et al.. We show that this category hypothesis is sufficient to get: (i) For every k/spl ges/2, NP-btt(k)-completeness is stronger than NP-btt(k+1)-completeness. (ii) For every k/spl ges/1, NP-bT(k)-completeness and NP-btt(k+1)-completeness are both stronger than NP-bT(k+1)-completeness. (iii) NP-btt-completeness is stronger than NP-tt-completeness.

We compare the weak completeness notions for E in the sense of Lutz's resource-bounded measure theory (1992) with respect to the standard polynomial time reducibilities. Our results parallel results for classical completeness by Watanabe (1987) and others. We show that the weak completeness notions for 1-query reductions coincide: A set is weakly complete for E under 1-truth-table reducibility iff it is weakly complete for length-increasing one-one reducibility. For most of the other polynomial reducibilities, however, we obtain separations of the weak completeness notions where these reducibilities differ on E (Ladner et al. (1975)). In fact our separations simultaneously hold for the corresponding weak completeness notions for E and E/sub 2/, for the classical completeness notions, and for the weak completeness notions in the sense of the resource-bounded Baire category concepts of Ambos-Spies et al. (1988) and Ambos-Spies (1995).

Abstract We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e.wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to thepmdegrees require no new complexity-theoretic results. The fact that thepm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21].

Abstract We show that the partial order of -sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

The problem of characterizing the finite lattices which can be embedded into the recursively enumerable degrees has a long history, which is summarized in [AL]. This problem is an important one, as its solution is necessary if a decision procedure for the ∀∃-theory of the poset of recursively emumerable degrees is to be found. A recursive nonembeddability condition, NEC, which subsumes all known nonembeddability conditions was presented in [AL]. This paper focuses on embeddability. An embeddability condition, EC, is introduced, and we prove that every finite lattice having EC can be embedded (as a lattice) into . EC subsumes all known embeddability conditions. EC is a Π3 condition which states that certain obstructions to proving embeddability do not exist. It seems likely that the recursive labeled trees used in EC can be replaced with trees which are effectively generated from uniformly defined finite trees, in which case EC would be equivalent to a recursive condition. We do not know whether EC and NEC are complementary. This problem seems to be combinatorial, rather than recursion-theoretic in nature. Our efforts to find a finite lattice satisfying neither EC nor NEC have, to this point, been unsuccessful. It is the second author's conjecture that the techniques for proving embeddability which are used in this paper cannot be refined very much to obtain new embeddability results. EC is introduced in §2, and the various conditions and definitions are motivated by presenting examples of embeddable lattices and indicating how the embedding proof works in those particular cases. The embedding construction is presented in §3, and the proof in §4.

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings. Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property(SUSP) if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property. In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP.

The classification of algebraic structures which can be embedded into ℛ, the uppersemilattice of recursively enumerable degrees, is the key to answering certain questions about Th(ℛ), the elementary theory of ℛ. In particular, these classification problems are important for answering decidability questions about fragments of Th(ℛ). Thus the solutions of Fried berg [F] and Mučnik [M] to Post's problem were easily extended to show that all finite partially ordered sets are embeddable into ℛ, and hence that ∃1 ∩ Th(ℛ), the existential theory of ℛ, is decidable. (The language used is ℒ′, the pure predicate calculus together with a binary relation symbol ≤ to be interpreted as the ordering of ℛ) The problem of determining which finite lattices are embeddable into ℛ has been a long-standing open problem, and is one of the major obstacles to determining whether ∀2 ∩ Th(ℛ), the universal-existential theory of ℛ, is decidable. Shore has obtained some nice partial results in this direction. Embeddings also played a central role in showing that Th(ℛ) is not ℵ0-categorical (Lerman, Shore and Soare [LeShSo]), thus resolving a problem posed by Jockusch. Harrington and Shelah [HS] embedded all 0′-presentable partially ordered sets into ℛ in such a way that the partially ordered sets can be uniformly recovered from four parameters. They used these embeddings to show that Th(ℛ) is undecidable. The first nontrivial extension of the embeddings of Friedberg and Mučnik to lattice embeddings was obtained independently by Lachlan [La1] and Yates [Y] who showed that the four-element Boolean algebra can be embedded into ℛ. Thomason [T] and Lerman independently extended this result to include all finite distributive lattices. The nondistributive case, however, was much more difficult. Lachlan [La2] embedded the two five-element nondistributive lattices M5 and N5 (see Figures 1 and 2) into ℛ, and his proof could easily have been extended to include a larger class of lattices.

We show that there is a recursive nonzero Karp (polynomial time many-one) degree which is not supremum of a minimal pair, i.e. of an incomparable pair of degrees with infimum 0, the degree of polynomial time computable sets. By existence of minimal pairs, this implies that there are nonisomorphic initial segments of Karp degrees.

We show that recursive ascending sequences of polynomial time (p-) degrees do not possess minimal upper bounds; that, for every nonzero p-degree a, there is a lesser nonzero p-degree b which does not help a; and that every nonzero p-degree is half of a minimal pair.

Lachlan's nondiamond theorem [7, Theorem 5] asserts that there is no embedding of the four-element Boolean algebra (diamond) in the recursively enumerable degrees which preserves infima, suprema, and least and greatest elements. Lachlan observed that, essentially by relativization, the theorem can be extended to Using the Sacks splitting theorem he concluded that there exists a pair of r.e. degrees which does not have an infimum, thus showing that the r.e. degrees do not form a lattice. We will first prove the following extension of (1): where an r.e. degree a is non-b-cappable if . From (2) we obtain more information about pairs of r.e. degrees without infima: For every nonzero low r.e. degree there exists an incomparable one such that the two degrees do not have an infimum and there is an r.e. degree which is not half of a pair of incomparable r.e. degrees which has an infimum in the low r.e. degrees. Probably the most interesting corollary of (2) is that the join of any cappable r.e. degree (i.e. half of a minimal pair) and any low r.e. degree is incomplete. Consequently there is an incomplete noncappable degree above every incomplete r.e. degree. Cooper's result [3] that ascending sequences of uniformly r.e. degrees can have minimal upper bounds in the set R of r.e. degrees is another corollary of (2).