In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

A subspace V of an infinite dimensional fully effective vector space V ∞ is called decidable if V is r.e. and there exists an r.e. W such that $V \oplus W = V_\infty$ . These subspaces of V ∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V ∞ ) and the set of decidable subspaces forms a lower semilattice S(V ∞ ). We analyse S(V ∞ ) and its relationship with L(V (...) ∞ ). We show: Proposition. Let U, V, W ∈ L(V ∞ ) where U is infinite dimensional and $U \oplus V = W$ . Then there exists a decidable subspace D such that U |oplus D = W. Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces. These results allow us to show: Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V ∞ )), is undecidable. This contrasts sharply with the result for recursive sets. Finally we examine various generalizations of our results. In particular we analyse S * (V ∞ ), that is, S(V ∞ ) modulo finite dimensional subspaces. We show S * (V ∞ ) is not a lattice. (shrink)

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Informal construction -- Formal construction -- Limiting results.

We investigate the relationship of the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low 2.

We investigate operators which take a set X to a set relatively computably enumerable in and above X by studying which such sets X can be so mapped into the Turing degree of K. We introduce notions of nontriviality for such operators, and use these to study which additional properties can be required of sets which can be completed to the jump by given operators of this kind.

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.

We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 (...) 0 complete. We also look at computable presentability of these classes. (shrink)

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)

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

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)

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...) c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

We examine the multiplicity of complementation amongst subspaces of V ∞ . A subspace V is a complement of a subspace W if V ∩ W = {0} and (V ∪ W) * = V ∞ . A subspace is called fully co-r.e. if it is generated by a co-r.e. subset of a recursive basis of V ∞ . We observe that every r.e. subspace has a fully co-r.e. complement. Theorem. If S is any fully co-r.e. subspace then S has (...) a decidable complement. We give an analysis of other types of complements S may have. For example, if S is fully co-r.e. and nonrecursive, then S has a (nonrecursive) r.e. nowhere simple complement. We impose the condition of immunity upon our subspaces. Theorem. Suppose V is fully co-r.e. Then V is immune iff there exist M 1 , M 2 ∈ L(V ∞ ), with M 1 supermaximal and M 2 k-thin, such that $M_1 \oplus V = M_2 \oplus V = V_\infty$ . Corollary. Suppose V is any r.e. subspace with a fully co-r.e. immune complement W (e.g., V is maximal or V is h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such that $V \oplus W = M \oplus W = D \oplus W = V_\infty$ . We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspace V of V ∞ is nowhere sound if (i) for all Q ∈ L(V ∞ ) if $Q \supset V$ then Q = V ∞ , (ii) V is immune and (iii) every complement of V is immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces. (shrink)

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.

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.

Rigorous formal proof is one of the key techniques in the natural sciences, engineering, and of course also in the formal sciences. Progress in automated reasoning increasingly enables computer systems to support, and even teach, users to conduct formal a.