TR00-024 Authors: Amihood Amir, Richard Beigel, William Gasarch

Publication: 22nd May 2000 10:39

Downloads: 2144

Keywords:

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

d(n)+O(1).