next up previous
Next: Bibliography Up: Project Description Previous: Query Order

Downward Collapses

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 $k>2$) the issue of whether the $k$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