Next: Bibliography
Up: Project Description
Previous: Query Order
The theory of NP-completeness does not resolve the issue of whether P
and NP are equal. However, it does unify the issues of whether
thousands of natural problems--the NP-complete problems--have
deterministic polynomial-time algorithms. The study of downward
collapse is similar in spirit. By proving downward collapses, we seek
to tie together central open issues regarding the computing power of
complexity classes. For example, one result obtained as part of this
project shows that (for
) the issue of whether the
th level of
the polynomial hierarchy is closed under complementation is identical
to the issue of whether two queries to this level give more power than
one query to this level.
Lane A. Hemaspaandra
2011-03-11