Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.

We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...) characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms (...) of the DTIME ) and NP. (shrink)

The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)

We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...) is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.