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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
9988310
Program Officer
David Du
Project Start
Project End
Budget Start
2000-09-01
Budget End
2004-08-31
Support Year
Fiscal Year
1999
Total Cost
$229,475
Indirect Cost
Name
Boston University
Department
Type
DUNS #
City
Boston
State
MA
Country
United States
Zip Code
02215