In this talk we will talk about these 'tameness' conditions (examples are the Sacks property, Laver property and others) and how they relate to the cardinal characteristics of localization and prediction.
In this talk, we'll look at this question. Right from the start we run into difficulty even phrasing the question precisely: If our underlying set A is a set of natural numbers, everything is trivially computable, and if it's not then we need to find the right notion of "compute." We'll discuss what this should be, and sketch the proof that in a precise sense, the answer to the above question is no.
Let p(x,y) = x5 - (2y+1) x3 - (y2+2) x2 + y(y-1)x + y3. Is it true that for every integer y ≥ 4, p(x, y) is an irreducible polynomial in Q[x], whereby we can determine its Galois group?
We encounter questions like this in our quest to achieve complexity classifications for counting problems, in the world of P versus NP. In this talk I will outline a proof to the first question (using character theory), and describe at a high level how answers to such questions lead to complexity dichotomy theorems, which classify ALL problems in a complexity class as either computable in polynomial time, or as hard as #P, which is harder than NP. I will give an overview of the status of the Classification Program for Counting Problems, including all partition functions for graph homomorphisms, counting constraint satisfaction problems, and Holant problems.
In this talk, I will describe another natural structural characterization of the continuous degrees. Kalimullin introduced the notion of a K-pair in order to define the enumeration jump. K-pairs, which can be thought of as "robust minimal pairs", play a part in almost all known definability results in the enumeration degrees. Indeed, they were used to define totality, and hence almost totality. We show that the non-continuous enumeration degrees are exactly the halves of nontrivial K-pairs relative to some (total) degree. Along with the earlier definition of the continuous degrees, this gives us a structural dichotomy in the enumeration degrees.
This talk is on joint work with Ganchev, Kalimullin, and Soskova.
This is is joint work with Stevo Todorčević.
In joint work with Ekaterina Fokina and Luca San Mauro we investigate a related notion, bi-embeddability spectra. Two structures are bi-embeddable if each is embeddable in the other and the bi-embeddability spectrum of a structure is the set of Turing degrees of its bi-embeddable copies. We give general results on bi-embeddability spectra and investigate bi-embeddability spectra of strongly locally finite graphs.
In 2014, M. Cai, Lempp, J. Miller and Soskova discovered an unusual structural property of the continuous degrees: if we join a continuous degree with a total degree that is not below it then the result is always a total degree. We call degrees with this curious property almost total. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of the enumeration degrees, this implies that the continuous degrees are also definable. Applying earlier work of J. Miller on the continuous degrees, this shows that the relation "PA above" on the total degrees is definable in the enumeration degrees.
In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. Like them, we identify our almost total degree as the degree of a point in a computably regular space with a computable dense sequence, and then we apply the effective version of Urysohn's metrization theorem to reveal our space as a computable metric space.
This is joint work with Uri Andrews, Greg Igusa, and Joseph Miller.
In joint work with Harrison-Trainor, we use these ideas to define a class of structures being universal within finitely generated structures. We then use small cancelation techniques from group theory to show that the class of finitely generated groups with finitely many constants named is universal within finitely generated structures.
I will discuss some results on the computability theory and reverse mathematics of theorems concerning basic model-theoretic notions such as atomic, homogeneous, and saturated models, including connections with combinatorial principles, and with first-order principles such as forms of induction restricted to formulas of low complexity. I will draw in particular from my recent paper "Induction, bounding, weak combinatorial principles, and the Homogeneous Model Theorem" with Karen Lange and Richard Shore.