next up previous
Next: Downward Collapses Up: Project Description Previous: Project Description

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.



Lane A. Hemaspaandra 2011-03-11