期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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).
