Bounded Query Functions with Limited Output Bits

Authors: R. Chang and J. S. Squire
Cite as: In Proceedings of the 16th IEEE Conference on Computational Complexity, 90-98, June 2001.
Previous incarnations: none.
Most readable version: conference version.
Status: journal version under preparation.
On-line:
- Conference paper (with small modifications) (PDF 419kbytes).
- Slides from the conference talk (PDF 108kbytes).

Abstract:

This paper explores the difference between parallel and serial queries to an NP-complete oracle, SAT, from the perspective of functions with a limited number of output bits. For polynomial-time bounded query language classes, which can be considered as functions with 1-bit output, previous work has shown that 2 serial queries to SAT is equivalent to 3 parallel queries to SAT. In contrast, for function classes with no limit on the number of output bits, previous work has shown that there exists a function that can be computed in polynomial time using 3 parallel queries to SAT, but cannot be computed using 2 serial queries to SAT, unless P = NP. The results in this paper show that there exists a function with 2-bit output that can be computed using 3 parallel queries to SAT, but cannot be computed using 2 serial queries to SAT, unless the Polynomial Hierarchy collapses.

Last Modified: 25 Nov 2003 23:37:51 EST by Richard Chang