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 part of the developing science base needed to guide, harness and exploit the explosively growing computer technology. The ultimate goal, which seems very hard to reach and which motivates most of this research, is a complete understand what is and is not feasibly computable. One of the main goals of complexity theory is to develop a classification of computational problems by the amount of computational resources needed to solve them. This classification leads to complexity classes consisting of all computations that can be solved within a given resource bound. This research project concentrates on the study of various complexity classes, relations between these classes and the internal structure of these classes. Of particular interest is understanding what makes problems hard to compute and to develop techniques to verify the degree of hardness. Also studied are trade-offs between various computational resources in problem solving, with particular attention to the relations and trade-offs between sequential-time, parallel-time, nondeterministic-time and memory requirements.
