Richard A. Shore

My major research interests have centered around analyzing the structures of relative complexity of computation of functions on the natural numbers. The primary measure of such complexity is given by Turing reducibility: f is easier to compute than g, if there is a (Turing) machine which can compute f if it is given access to the values of g. I have also worked with various other interesting measures of complexity that are defined by restricting the resources available primarily in terms of access to g. The general thrust of my work has been to show that these structures are as complicated as possible both algebraically and logically (in terms of the complexity of the decision problems for their theories). These results also allow one to differentiate among different notions of relative complexity in terms of the orderings they define.

Another major theme in my work has been the relationship between these notions of computational complexity and ones based on the difficulty of defining functions in arithmetic. Restricting the computational resources more directly in terms of time or space leads out of recursion theory and into complexity theory. Relaxing the restrictions by allowing various infinitary procedures leads instead into generalized recursion theory and set theory.

I have also worked on issues in effective model theory and algebra connected with the problem of how the computational properties of algebraic structures can vary with different (but always computable) presentations of the models. The methods developed in many of these investigations are also useful in determining the effective content of standard mathematical theorems (when can existence proofs be made effective) and the inherent difficulty of combinatorial theorems in proof as well as complexity theoretic terms. Recently, I have been working on classifying results in algebra, combinatorics and logic in these “reverse mathematics” settings. I have been particularly interested in ones that are incomparable with the standard theories typically found in such work. Another interesting current application of these approaches has been to produce very elementary proofs of Ramsey type combinatorial theorems that previously only had proofs using ultrafilters and other even high order notions and structures.