- Authors: R. Beigel and R. Chang
- Cite as:
Information and Computation, 166(1):71-91, 2001.
- Previous incarnations:
- In Proceedings of the 5th Israeli Symposium
on Theory of Computing and Systems, 159-165, June 1997.
- Most readable version:
- Status: complete.
We consider polynomial-time Turing machines that have access to two
oracles and investigate when the order of oracle queries is
significant. The oracles used here are complete languages for the
Polynomial Hierarchy (PH). We prove that, for solving decision
problems, the order of oracle queries does not matter. This improves
upon the previous result of Hemaspaandra, Hemaspaandra and Hempel, who
showed that the order of the queries does not matter if the base
machine asks only one query to each oracle. On the other hand, we
prove that, for computing functions, the order of oracle queries does
matter, unless PH collapses.
29 Oct 2007 20:20:10 EDT