Algorithmic Randomness and Computable Model Theory

One of the major questions of computable model theory is that of algorithmic complexity of various presentations of an algebraic structure. To characterize the degrees of isomorphic copies of a given structure, we use the notion of the degree spectra of a structure. The degree spectra of structures with various computability and model- theoretic properties have been studied by many authors. A connected question is that of characterizing the complexity of an additional relation on a computable structure. The notion of a degree spectrum of a relation reflects the difference in algorithmic properties between various computable presentations of the same algebraic structure. There has been some work done connecting both notions of degree spectra. Algorithmic randomness is another important direction of computability theory. The main question is: what does it mean for a set of natural numbers (or, equivalently, for a real) to be random, and how is the randomness of a set related to ist computational strength? Various classes of real numbers connected with the notion of randomness have been investigated (e.g., degrees containing a Martin-Löf real, DNC degrees, or PA degrees). The current project connects the questions from computable model theory and algorithmic randomness. We ask if there exist structures with degree spectra consisting exactly of DNC degrees or exactly of PA degrees. We also study a similar question of existence of computable structures and additional relations on them such that the degree spectrum of the relation consists precisely of DNC degrees or PA degrees, or degrees containing Martin-Löfreal, etc. Furthermore, we aim to find a characterization of n-randomness and n-genericity in terms of structures. Thus, on the one hand, this project will provide new examples of algebraic structures with interesting computability-theoretic properties. On the other hand, it will give a new interesting characterization of known classes of degrees studied in the area of algorithmic randomness.

The project deals with two main topics. The primary work was on the interaction of randomness and computability. With various collaborators, we solved the long open Covering Problem for Martin-Löf randomness by studying the interaction of randomness and analysis. A number of related results came out of this work as well. We also did work in linear orders, equivalence relations, and effective versions of the Axiom of Choice. In linear orders, there is an old result of Watnik and Ash for countable linear orders. With collaborators, we discovered and proved the generalization for larger linear orders. In equivalence relations, we studied hyperarithmetic isomorphism of computable structures. With collaborators, we showed that this equivalence relation is naturally Pi-1-1-complete. This is the first natural example of a relation complete at this level. The particular version of the Axiom of Choice studied is called the Finite Intersection Principle, and involves families of intersecting sets. The principle states that such families always exist. With collaborators, we investigated the computational complexity of finding such a family. We showed that, in certain circumstances, finding such a family is exactly as hard as finding a 1-generic. Later work by others removed the qualification and generalized this to all circumstances. The second topic was parameterized complexity theory. It offers a framework for a more finegrained complexity analysis of computational problems. Problem instances come along with a natural number, their parameter, and computational resources used by an algorithm are measured by functions in the inputs length as well as its parameter. Parameterized time and space complexity are well established research fields. We gave a theoretical foundation for a parameterized analysis of random complexity and proves various parameterized analogues of classical results. We suggested a new way how parameterizations can be introduced to propositional proof complexity. We defined natural parameterized versions of the most important strong propositional proof systems and compared their relative strength via a newly introduced notion of simulation. We also studied the question to what extent it is possible to feasibly produce problem instances which are hard for a given algorithm or proof system. We obtained some positive and some negative results. We proved a model-theoretic preservation theorem for quantified constraint satisfaction problems on certain well-behaved infinite databases. This is vital for an algebraic approach to constraint satisfaction complexity, so successful in the unquantified setting.