Juris Hartmanis
Walter R. Read Professor of Engineering
Turing Award Winner
http://www.cs.cornell.edu/Info/ Annual96/Faculty/jh.html
Ph.D. California Institute of Technology, 1955

The strategic goal of our research is to contribute to the development of a comprehensive theory of computational complexity. Computational complexity, the study of the quantitative laws that govern computation, is an essential part of the science base needed to guide, harness, and exploit the explosively growing computer technology.

Our research has two main goals: a) to understand better what makes problems hard to compute and to develop techniques to verify the degree of hardness, and b) to explore what is the best that can be done with computational resources that are not sufficient to solve a problem.

Computational complexity classifies problems by the amounts of various computational resources needed to solve them. This classification yields complexity classes, each of which consists of all problems that can be solved within a given computational resource bound. To gain a deeper understanding of what makes problems hard to compute, we explore various complexity classes, relations between these classes, and the internal structure of these classes. We also study the trade-offs between different computational resources, with particular attention to sequential-time, parallel-time, nondeterministic-time, memory requirements, randomness as a computational resource, and interactive computing.


University Activities

Professional Activities



Return to:
1995-1996 Annual Report Home Page
Departmental Home Page

If you have questions or comments please contact: www@cs.cornell.edu.

Last modified: 2 November 1996 by Denise Moore (denise@cs.cornell.edu).