We consider polynomial-time Turing machines which have access to two
oracles and investigate when the order of oracle access is significant.
The oracles used here are complete languages for the Polynomial Hierarchy
(\PH). For language classes, we show that the order of the oracle queries
does not matter, even when the queries are truth table queries. This
improves upon the previous results of Hemaspaandra, Hemaspaandra and Hempel
who showed that the order of the queries does not matter if the base
machine asks one query to each oracle.
For k > j, let H and E be complete languages for the k-th and j-th levels
of PH, respectively. Then, our results show that for all polynomial
bounded r(n) and s(n), languages recognizable by polynomial-time Turing
machines which ask at most r(n) truth table queries to H followed by s(n)
truth table queries to E can also be recognized by polynomial-time Turing
machines that ask s(n) queries to E first, followed by r(n) queries to H.
In fact, all of the queries can be made in parallel.
On the other hand, we prove that, for computing functions, the order of
oracle queries does matter, unless PH collapses. In particular, for all
constants r and s, unless PH collapses to the (j+1)-th level, there exists
a function that is computable by a polynomial time Turing machine which
asks r truth-table queries to H followed by s truth-table queries to E that
is not computable by any polynomial-time Turing machine which reverses the
order of the queries to E and H.
This talk presents joint work with Richard Beigel.