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:
- Status: journal version under preparation.
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.
25 Nov 2003 23:37:51 EST