Downward Collapses and Query Order
Everyone knows that it makes more sense to
first look up in your on-line datebook the date of the yearly
Computational Complexity conference and then phone your travel agent
to get tickets, as opposed to first phoning your travel agent (without
knowing the date) and then consulting your on-line date book to find
the date. In real life, order matters.
This project seeks to determine whether one's everyday-life intuition
that order matters carries over to complexity theory. Does the order
in which one accesses computational information sources matter? In
particular, we study the importance of the order of queries when
accessing two sets from the boolean hierarchy, and we also study the
importance of the order of queries when accessing two sets from the
polynomial hierarchy.
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.
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form) papers, from or related to this project, by
University of Rochester authors. Essentially all the papers listed below can
be found, in their full technical report versions, in the
UR-CS Technical Report Archive's theory
section. Lane
Hemaspaandra's complete publication list can always be found at
http://www.cs.rochester.edu/u/lane/publist.pdf.
- 2
-
R. Beigel, R. Chang, and M. Ogiwara.
A relationship between difference hierarchies and relativized
polynomial hierarchies.
Mathematical Systems Theory, 26(3):293-310, 1993.
- 3
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
An introduction to query order.
Bulletin of the EATCS, 63:93-107, 1997.
- 4
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Query order in the polynomial hierarchy.
Journal of Universal Computer Science, 4(6):574-588, 1998.
- 5
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
R
(NP) distinguishes robust
many-one and Turing completeness.
Theory of Computing Systems, 31(3):307-325, 1998.
- 6
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
What's up with downward collapse: Using the easy-hard technique to
link boolean and polynomial hierarchy collapses.
SIGACT News, 29(3):10-22, 1998.
- 7
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
A downward collapse within the polynomial hierarchy.
SIAM Journal on Computing, 28(2):383-393, 1999.
- 8
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Using the no-search easy-hard technique for downward collapse.
Technical Report TR-752, Department of Computer Science, University
of Rochester, Rochester, NY, June 2001.
- 9
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Extending downward collapse from 1-versus-2 queries to
-versus-
queries.
SIAM Journal on Computing, 34(6):1352-1369, 2005.
- 10
-
L. Hemaspaandra, H. Hempel, and G. Wechsung.
Query order.
SIAM Journal on Computing, 28(2):637-651, 1999.
- 11
-
L. Hemaspaandra and S. Jha.
Defying upward and downward separation.
Information and Computation, 121(1):1-13, 1995.
Lane A. Hemaspaandra