Richard A. Shore, Cornell University
Professor
Ithaca, New York
shore@cornell.edu
Office:
(607) 255-4081
Bio/Research
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 comp...
Click to Expand >>
Click to Expand >>
Bio/Research
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.
Click to Shrink <<
Click to Shrink <<