Next: Downward Collapses
Up: Project Description
Previous: Project Description
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.
Lane A. Hemaspaandra
2011-03-11