Computability and Complexity

Rod Downey took up a lectureship in mathematics at the Victoria University of Wellington in 1986. At the time he was a promising young researcher with a dozen papers to his name. Thirty years on, the dozen has mushroomed into 250-plus as he has developed into a world leader in his field who has made a profound contribution to the mathematical research environment both internationally and in New Zealand. This article briefly outlines his exceptional career.

I wish Rod a happy birthday. Rod has offered a good historical account of our early days of collaboration in his paper, “The Birth and Early Days of Parameterized Complexity” [D12]. One of the themes of our life-long collaboration has been a shared passion for surfing, and many of our best ideas were hammered out on surf trips. This contribution is best viewed as a gloss on that earlier account by Rod, taking as an organizing skeleton, our various surf trips and what we were thinking about, with a particular emphasis on open problems and horizons that remain, and some reflections on the formation of our research community.

Rod Downey has a long career of important discoveries in the recently developed subjects of computability and computer science. These remarks were delivered by invitation at the 50th anniversary celebration of the founding of the Computer Science Department at Cornell. This was a time of transition from computers and computer programming to computer science.

In honor of Rod Downey’s 60th birthday, this paper discusses a few open problems connected in one way or another with him.

We survey results on these concepts, discover surprising similarities, and, in particular explain why autoreducibility might someday separate complexity classes.

Given a string, what is its complexity? We survey what is known about the computational complexity of this problem, and describe several open questions.

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol only allows a bounded number of stack movements. BPD automata are a natural real-time restriction of pushdown automata. We show that BPD dimension is a robust notion by giving an equivalent characterization of BPD dimension in terms of BPD compressors. We then study the relationships between BPD compression, and the standard Lempel-Ziv (LZ) compression algorithm, and show that in contrast to the finite-state compressor case, LZ is not universal for bounded pushdown compressors in a strong sense: we construct a sequence that LZ fails to compress significantly, but that is compressed by at least a factor 2 by a BPD compressor. As a corollary we obtain a strong separation between finite-state and BPD dimension.

Rod Downey and I have had a fruitful relationship though direct and indirect collaboration. I explore two research directions, the limitations of distillation and instance compression, and whether or not we can create NP-incomplete problems without punching holes in NP-complete problems.

Rod’s accomplishments as a mathematician are well-known to many in his area, and there are perhaps many others who are able to describe his numerous astonishing contributions to mathematical logic. My aim here is to say something about my experiences of being his graduate student, and to describe in some detail a non-mathematical side of the man.

We give an exposition of Herrmann’s proof that there is an infinite computable partial ordering with no infinite $$\Sigma ^0_2$$ chains or antichains.

We consider the strength and effective content of restricted versions of Hindman’s Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $$\mathsf {HT}^{\le n}_k$$ denote the assertion that for each k-coloring c of $$\mathbb {N}$$ there is an infinite set $$X \subseteq \mathbb {N}$$ such that all sums $$\sum _{x \in F} x$$ for $$F \subseteq X$$ and $$0 < |F| \le n$$ have the same color. We prove that there is a computable 2-coloring c of $$\mathbb {N}$$ such that there is no infinite computable set X such that all nonempty sums of at most 2 elements of X have the same color. It follows that $$\mathsf {HT}^{\le 2}_2$$ is not provable in $$\mathsf {RCA}_0$$ and in fact we show that it implies $$\mathsf {SRT}^2_2$$ in $$\mathsf {RCA}_0+ \mathsf {B}\Pi ^0_1$$. We also show that there is a computable instance of $$\mathsf {HT}^{\le 3}_3$$ with all solutions computing $$0'$$. The proof of this result shows that $$\mathsf {HT}^{\le 3}_3$$ implies $$\mathsf {ACA}_0$$ in $$\mathsf {RCA}_0$$.

Matroids generalize the familiar notion of linear dependence from linear algebra. Following a brief discussion of founding work in computability and matroids, we use the techniques of reverse mathematics to determine the logical strength of some basis theorems for matroids and enumerated matroids. Next, using Weihrauch reducibility, we relate the basis results to combinatorial choice principles and statements about vector spaces. Finally, we formalize some of the Weihrauch reductions to extract related reverse mathematics results. In particular, we show that the existence of bases for vector spaces of bounded dimension is equivalent to the induction scheme for $$\varSigma ^0_2$$ formulas.

We study the proof strength of various second order logic principles that make statements about families of sets and functions. Usually, families of sets or functions are represented in a uniform way by a single object. In order to be able to go beyond the limitations imposed by this approach, we introduce the concept of weakly represented families of sets and functions. This allows us to study various types of families in the context of reverse mathematics that have been studied in set theory before. The results obtained witness that the concept of weakly represented families is a useful and robust tool in reverse mathematics.

We study the uniform computational content of the Vitali Covering Theorem for intervals using the tool of Weihrauch reducibility. We show that a more detailed picture emerges than what a related study by Giusto, Brown, and Simpson has revealed in the setting of reverse mathematics. In particular, different formulations of the Vitali Covering Theorem turn out to have different uniform computational content. These versions are either computable or closely related to uniform variants of Weak Weak Kőnig’s Lemma.

We study the principle of positive choice in the Weihrauch degrees. In particular, we study its behaviour under composition and jumps, and answer three questions asked by Brattka, Gherardi and Hölzl.

The notions we study in this paper, those of existentially-atomic structure and effectively existentially-atomic structure, are not really new. The objective of this paper is to single them out, survey their properties from a computability-theoretic viewpoint, and prove a few new results about them. These structures are the simplest ones around, and for that reason alone, it is worth analyzing them. As we will see, they are the simplest ones in terms of how complicated it is to find isomorphisms between different copies and in terms of the complexity of their descriptions. Despite their simplicity, they are very general in the following sense: every structure is existentially atomic if one takes enough jumps, the number of jumps being (essentially) the Scott rank of the structure. That balance between simplicity and generality is what makes them important.

A computable ring is a ring equipped with a mechanical procedure to add and multiply elements. In most natural computable integral domains, there is a computational procedure to determine if a given element is prime/irreducible. However, there do exist computable UFDs (in fact, polynomial rings over computable fields) where the set of prime/irreducible elements is not computable. Outside of the class of UFDs, the notions of irreducible and prime may not coincide. We demonstrate how different these concepts can be by constructing computable integral domains where the set of irreducible elements is computable while the set of prime elements is not, and vice versa. Along the way, we will generalize Kronecker’s method for computing irreducibles and factorizations in $$\mathbb {Z}[x]$$.

Inspired by recent work of Csima and Harrison-Trainor and of Montalbán in relativizing the notion of degrees of categoricity, we return to uniform computable categoricity, as described in work of Downey, Hirschfeldt and Khoussainov. Our attempt to integrate these notions together leads to certain new questions about relativizing the concept of the jump of a structure, as well as to an idea of the structural information content of a countable structure, i.e., that information which can be recovered uniformly from copies of the structure.

The relationship between enumeration degrees and abstract models of computability inspires a new direction in the field of computable structure theory. Computable structure theory uses the notions and methods of computability theory in order to find the effective contents of some mathematical problems and constructions. The paper is a survey on the computable structure theory from the point of view of enumeration reducibility.

We survey the current results about degrees of categoricity and the degrees that are low for isomorphism as well as the proof techniques used in the constructions of elements of each of these classes. We conclude with an analysis of these classes, what we may deduce about them given the sorts of proof techniques used in each case, and a discussion of future lines of inquiry.

The purpose of this paper to review the results on the constructive nilpotent groups, not claiming to be complete. We consider both the fundamental questions, which are general in the computable algebra, such as the problems of existence, uniqueness, and extension of constructivizations (computable copies), and the questions that arise from the study of the effectiveness of the basic theorems, constructions and structural properties within the class of nilpotent groups.

This paper is a survey of results together with a list of open questions on $$\Sigma $$–definability of structures over $$\mathbb {HF}(\mathbb {R})$$, the hereditarily finite superstructure over the ordered field of the real numbers.

We survey fundamental notions and results in the study of the lattice of computably enumerable vector spaces and its quotient lattice modulo finite dimension. These lattices were introduced and first studied by Metakides and Nerode in the late 1970s and later extensively investigated by Downey, Remmel and others. First, we focus on the role of the dependence algorithm, the effectiveness of the bases, and the Turing degree-theoretic complexity of the dependence relations. We present a result on the undecidability of the theories of the above lattices. We show the development of various notions of maximality for vector spaces, and role they play in the study of lattice automorphisms and automorphism bases. We establish a new result about the role of supermaximal spaces in the quotient lattice automorphism bases. Finally, we discuss the problem of finding orbits of maximal spaces and the recent progress on this topic.

An injection structure $${\mathcal A}= (A,f)$$ is a set A together with a one-place one-to-one function f. $${\mathcal A}$$ is an FST injection structure if A is a regular set, that is, the set of words accepted by some finite automaton, and f is realized by a finite-state transducer. We initiate the study of FST injection structures. We show that the model checking problem for FST injection structures is undecidable which contrasts with the fact that the model checking problem for automatic relational structures is decidable. We also explore which isomorphisms types of injection structures can be realized by FST injections. For example, we completely characterize the isomorphism types that can be realized by FST injection structures over a unary alphabet. We show that any FST injection structure is isomorphic to an FST injection structure over a binary alphabet. We also prove a number of positive and negative results about the possible isomorphism types of FST injection structures over an arbitrary alphabet.

We review the literature on universal computably enumerable equivalence relations, i.e. the computably enumerable equivalence relations (ceers) which are $$\Sigma ^0_1$$-complete with respect to computable reducibility on equivalence relations. Special attention will be given to the so-called uniformly effectively inseparable (u.e.i.) ceers, i.e. the nontrivial ceers yielding partitions of the natural numbers in which each pair of distinct equivalence classes is effectively inseparable (uniformly in their representatives). The u.e.i. ceers comprise infinitely many isomorphism types. The relation of provable equivalence in Peano Arithmetic plays an important role in the study and classification of the u.e.i. ceers.

We first prove a theorem about reals (subsets of $$\mathbb {N}$$) and classes of reals: If a real X is $$\Sigma _{1}^{1}$$ in every member G of a nonempty $$\Sigma _{1}^{1}$$ class $$\mathcal {K}$$ of reals then X is itself $$\Sigma _{1}^{1}$$. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in $$\omega $$-logic. We then prove the analog of our first theorem for classes of reals: If a class $$\mathcal {A}$$ of reals is $$\Sigma _{1}^{1}$$ in every member of a nonempty $$\Sigma _{1}^{1}$$ class $$\mathcal {B}$$ of reals then $$\mathcal {A}$$ is itself $$\Sigma _{1}^{1}$$.

This paper is a survey on the upper semilattices of Turing and enumeration degrees of n-c.e. sets. Questions on the structural properties of these semilattices, and some model-theoretic properties are considered.

In this article, we will study the weak-truth-table (wtt, for short) degrees of d.c.e. sets and show that there is no maximal d.c.e. wtt-degree.

The automorphism group of the truth-table degrees with order and jump is fixed on the set of degrees above the fourth jump, $$\mathbf 0^{(4)}$$.

The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few easy proofs to illustrate the flavor of the subject.

Our focus will be on the computably enumerable (c.e.) sets and trivial, non-trivial, Friedberg, and non-Friedberg splits of the c.e. sets. Every non-computable set has a non-trivial Friedberg split. Moreover, this theorem is uniform. V. Yu. Shavrukov recently answered the question which c.e. sets have a non-trivial non-Friedberg splitting and we provide a different proof of his result. We end by showing there is no uniform splitting of all c.e. sets such that all non-computable sets are non-trivially split and, in addition, all sets with a non-trivial non-Friedberg split are split accordingly.

We show that over the base system $$P^-+\Sigma _2$$-bounding, the existence of a 1-generic degree $$<\mathbf {0''}$$ bounding a minimal degree is equivalent to $$\Sigma _2$$-induction.

In this paper, we show that the so-called “double bubbles” are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees $$\mathbf{d}_1> \mathbf{d}_2 > \mathbf{0}$$ forms a double bubble if all d.c.e. degrees below $$\mathbf{d}_1$$ are comparable with $$\mathbf{d}_2$$.

We introduce and discuss some techniques designed for the study of the strongly bounded Turing degrees of the computably enumerable sets, i.e., of the computable Lipschitz degrees and of the identity bounded Turing degrees of c.e. sets. In particular we introduce some tools which allow the transfer of certain facts on the weak truth-table degrees to these degree structures. Using this approach we show that the first order theories of the partial orderings $$(\mathrm {R}_\mathrm {cl},\le )$$ and $$(\mathrm {R}_\mathrm {ibT},\le )$$ of the c.e. $$\mathrm {cl}$$- and $$\mathrm {ibT}$$-degrees are not $$\aleph _0$$-categorical and undecidable. Moreover, various other results on the structure of the partial orderings $$(\mathrm {R}_\mathrm {cl},\le )$$ and $$(\mathrm {R}_\mathrm {ibT},\le )$$ are obtained along these lines.

In the 1960s, Clement F. Kent showed that there are continuum many permutations of $$\omega $$ that map computable sets to computable sets. Thus these permutations preserve the bottom Turing degree 0. We show that a permutation of $$\omega $$ cannot induce any nontrivial automorphism of the Turing degrees of members of $$2^{\omega }$$, and in fact any permutation that induces the trivial automorphism must be computable.

We investigate which reals can never be L-random. That is to give a description of the reals which are always belong to some $$L[\lambda ]$$-null set for any continuous measure $$\lambda $$. Among other things, we prove that $$NCR_L$$ is an L-cofinal subset of $$Q_3$$ under $$ZFC+PD$$.

We show that given any non-computable left-c.e. real $$\alpha $$ there exists a left-c.e. real $$\beta $$ such that $$\alpha \ne \beta +\gamma $$ for all left-c.e. reals and all right-c.e. reals $$\gamma $$ . The proof is non-uniform, the dichotomy being whether the given real $$\alpha $$ is Martin-Löf random or not. It follows that given any universal machine U, there is another universal machine V such that the halting probability $$\Omega _U$$ of U is not a translation of the halting probability $$\Omega _V$$ of V by a left-c.e. real. We do not know if there is a uniform proof of this fact.

We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing $$\mathrm {DNR}$$ functions relative to X that compute no Martin-Löf random set. We show that the same holds when Martin-Löf randomness is replaced with effective bi-immunity. It follows that there are sequences of effective Hausdorff dimension 1 that compute no effectively bi-immune set.We also establish an important difference between the two properties. The class Low(MLR, EBI) of oracles relative to which every Martin-Löf random is effectively bi-immune contains the jump-traceable sets, and is therefore of cardinality continuum.

Let $$\alpha $$ and $$\beta $$ be (Martin-Löf) random left-c.e. reals with left-c.e. approximations $$\{\alpha _s\}_{s\in \omega }$$ and $$\{\beta _s\}_{s\in \omega }$$.

Let $$\varphi _i$$, $$i\in \mathbb {N}$$ be a standard enumeration of the 1-place partial recursive functions $$\varphi :\;\subseteq \mathbb {N}\rightarrow \mathbb {N}$$.

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a “good model” is introduced, a natural question arises: it is possible that for some piece of data there is no good model? If yes, how often these bad (non-stochastic) data appear “in real life”?Another, more technical motivation comes from algorithmic information theory. In this theory a notion of complexity of a finite object (=amount of information in this object) is introduced; it assigns to every object some number, called its algorithmic complexity (or Kolmogorov complexity). Algorithmic statistic provides a more fine-grained classification: for each finite object some curve is defined that characterizes its behavior. It turns out that several different definitions give (approximately) the same curve.Road-map: Sect. 2 considers the notion of $$(\alpha ,\beta )$$-stochasticity; Sect. 3 considers two-part descriptions and the so-called “minimal description length principle”; Sect. 4 gives one more approach: we consider the list of objects of bounded complexity and measure how far some object is from the end of the list, getting some natural class of “standard descriptions” as a by-product; finally, Sect. 5 establishes a connection between these notions and resource-bounded complexity. The rest of the paper deals with an attempts to make theory close to practice by considering restricted classes of descriptions (Sect. 6) and strong models (Sect. 7).In this survey we try to provide an exposition of the main results in the field (including full proofs for the most important ones), as well as some historical comments. We assume that the reader is familiar with the main notions of algorithmic information (Kolmogorov complexity) theory. An exposition can be found in [42, Chaps. 1, 3, 4] or [22, Chaps. 2, 3], see also the survey [36].A short survey of main results of algorithmic statistics was given in [41] (without proofs); see also the last chapter of the book [42].

Analytic concepts contribute to our understanding of randomness of reals via algorithmic tests. They also influence the interplay between randomness and lowness notions. We provide a survey.