Juris Hartmanis
Walter R. Read Professor of Engineering
PhD 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 is the study of the quantitative laws that govern computation, and it is an essential part of the science base needed to guide, harness, and exploit the explosively growing computer technology. 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 in problem solving, 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:
1994-1995 Annual Report Home Page
Departmental Home Page

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

Last modified: 24 November 1995 by Denise Moore (denise@cs.cornell.edu).