Richard A. Shore

Professor of Mathematics

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, f <T 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 such 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 or set theory. The methods developed in 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 theoretic terms.

Professional Activities:

Selected Publications: