Two complementary areas of computational complexity theory will be studied. The first is the complexity of quantum computing, a project that my colleagues and I have begun work on during the past two years. To this point two projects have been completed, both concern finding lower bounds for classes of quantum computations. I propose to continue to explore the power of quantum computation and try to obtain both lower and upper bounds by relating quantum classes to classical complexity theory. The second area concerns the study of the complexity theory of natural combinatorial functions in PSPACE. Here the goal is to make use of the extensions of the polynomial hierarchy, which were defined and explicated in an earlier paper on the hyperpolynomial hierarchy. Tools such as the NP-jump and the methods of Toda's theorem will be studied and extended in order to classify counting problems and other natural complex problems in PSPACE. We intend to explore this new framework for the classification of optimization problems and to study the relationship between older notion such as alternation and the extended polynomial hierarchies which we have defined.
