The strategic goal of this 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. The proposed 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, b) to explore what is the best that can be done with computational resources 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 that consist 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, the project explores various complexity classes, relations between these classes and the internal structure of these classes. It also explores 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.
