Search

As soon as Bennett and Gill first demonstrated that, relative to a randomly chosen oracle, P is not equal to NP with probability 1, the random oracle hypothesis began piquing the interest of mathematicians and computer scientists. This was quickly disproven in several ways, most famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using largeness with respect to the Ramsey forcing notion. In this new context, we demonstrate that the set of oracles separating NP and coNP is 'not small', and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. In a related set of results, we demonstrate that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

We prove various results about the complexity of countable structures, both computable and arbitrary.We begin by investigating descriptions of countable structures in the infinitary logic Lω1ω. Given a countable structure A, we can find a sentence ϕ, a Scott sentence for A, which describes A up to isomorphism in the sense that A is the unique countable model of ϕ. We can assign a complexity, the Scott rank of A, to A; this is the quantifier complexity of the simplest Scott sentence. We investigate the Scott ranks of the models of a theory; we produce several new computable models of high Scott rank; we construct a computable group with no d-Σ2 Scott sentence; and we produce a first-order theory of Ulm type.Next, we look at computable structures on a cone. If A is a natural structure—by which we mean an informal notion of a structure that might show up in the normal course of mathematics, and which was not constructed explicitly as a computability-theoretic counterexample—then arguments about A will generally relativize. So we can study natural structures by studying arbitrary structures relativized "on a cone". This gives us a way of making precise statements about the imprecise notion of a natural structure. We give a complete classification of the degrees of categoricity on a cone, and prove a number of results about degree spectra of relation on a cone.Third, we investigate the deep connections between infinitary interpretations and functors. An interpretation of one structure A in another structure B induces a functor which produces copies of A from copies of B. Moreover, the interpretation induces a homomorphism from the automorphism group of B to the automorphism group of A. We show that this reverses: given a functor from B to A, or a homomorphism from the automorphism group of B to A, we can recover an interpretation. We consider the effective version of this, as well as the corresponding results for bi-interpretations.Finally, we look at a number of different algebraic structures. We study the effectivization of extending automorphisms of fields to their algebraic closure, extending valuations to a field extension, and embedding valued fields into algebraically closed valued fields. We give a metatheorem for finding computable copies of various algebraic structures with an independence relation, such as differentially closed fields with δ-independence, with a computable basis. We show that there is a computable left-orderable group with no computable copy with a computable ordering.

SETS, MODELS, AND PROOFS: TOPICS IN THE THEORY OF RECURSIVE FUNCTIONS David Roger Belanger, Ph.D. Cornell University We prove results in various areas of recursion theory. First, in joint work with Richard Shore, we prove a new jump-inversion result for ideals of recursively enumerable (r.e.) degrees; this defeats what had seemed to be a promising tack on the automorphism problem for the semilattice R of r.e. degrees. Second, in work spanning two chapters, we calibrate the reverse-mathematical strength of a number of theorems of basic model theory, such as the Ryll-Nardzewski atomic-model theorem, Vaught's no-two-model theorem, Ehrenfeucht's three-model theorem, and the existence theorems for homogeneous and saturated models. Whereas most of these are equivalent over RCA0 to one of RCA0 , WKL0 , ACA0 , as usual, we also uncover model-theoretic statements with exotic complexities such as ¬WKL0 ∨ ACA0 and WKL0 ∨ I[SIGMA]0 . 2 Third, we examine the possible weak truth table (wtt) degree spectra of countable first-order structures. We find several points at which the wtt- and Turingdegree cases differ, notably that the most direct wtt analogue of Knight's dichotomy theorem does not hold. Yet we find weaker analogies between the two, including a new trichotomy theorem for wtt degree spectra in the spirit of Knight's.

We investigate the Martin-L�of random sample paths of Brownian motion, applying techniques from algorithmic randomness to Brownian motion, an active area of research in probability theory. In Chapter 2, we investigate many classical results about one dimensional Brownian motion in the context of Martin-L�of randomness. We show that many results which are known to hold almost surely for the Brownian motion process - including results concerning the modulus of continuity, points of increase, time inversion, and law of large numbers - hold for every Martin-L�of random sample path. We also show that scaling invariance and the strong Markov property hold for every Martin-L�of random path, with suitable effectivization. In Chapter 3, we investigate the zero set of one-dimensional Brownian motion. We prove that the set of zeroes is characterized by having high effective dimension. We also demonstrate that, although the zeroes are highly noncomputable in the sense of effective dimension, many of them are layerwise computable from a Brownian path. In Chapter 4, we give a new proof that the solution to the Dirichlet problem in the plane is computable. It is a well-known result of Kakutani that the solution to the Dirichlet problem can be found using expected hitting times of Brownian paths to the boundary. We show that the hitting times of Martin-L�of random Brownian paths on a computable boundary are layerwise computable in the path, and thus the expected value of the hitting times is computable, and so the solution to the Dirichlet problem is computable. In Chapter 5, we further investigate planar Martin-L�of random Brownian motion. We demonstrate that a Martin-L�of random planar Brownian path only hits points such that the path is not random relative to those points (except the origin), which implies that a Martin-L�of random planar path has area zero and that every point except the origin is hit by only measure 0 many paths. We also show that every Martin-L�of random planar Brownian path has points of uncountable multiplicity.