Commutative Queries

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: journal version.
Status: complete.
On-line:
- Article in Elsevier's Science Direct: DOI 10.1006/inco.2000.2918.
- Revised journal submission available as a PDF file (with embedded Type 1 fonts) order.pdf.
- Conference talk slides: slides.pdf.

Abstract:

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.

Last Modified: 22 Jul 2024 11:27:53 EDT by Richard Chang