ECCC-Report TR00-024https://eccc.weizmann.ac.il/report/2000/024Comments and Revisions published for TR00-024en-usMon, 22 May 2000 10:39:06 +0300
Paper TR00-024
| Some Connections between Bounded Query Classes and Non-Uniform Complexity |
Amihood Amir,
Richard Beigel,
William Gasarch
https://eccc.weizmann.ac.il/report/2000/024Let 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).
Mon, 22 May 2000 10:39:06 +0300https://eccc.weizmann.ac.il/report/2000/024