Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-024 | 16th May 2000 00:00

Some Connections between Bounded Query Classes and Non-Uniform Complexity


Authors: Amihood Amir, Richard Beigel, William Gasarch
Publication: 22nd May 2000 10:39
Downloads: 2144


Let A(x) be the characteristic function of A. Consider the function
F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be
computed with fewer than k queries to some set X, then A can be
computed by polynomial size circuits. A generalization of this result
has applications to bounded query classes, circuits, and
enumerability. In particular we obtain the following. (1) Assuming
Sigma_3^p <> Pi_3^p, there are functions computable using f(n)+1
queries to SAT that are not computable using f(n) queries to SAT, for
f(n) = O(logn). (2) If F_k^A, restricted to length n inputs, can be
computed by an unbounded fanin oracle circuit of size s(n) and depth
d(n), with k-1 queries to some set X, then A can be computed with an
unbounded fanin (non-oracle) circuit of size n^{O(k)}s(n) and depth

ISSN 1433-8092 | Imprint