Some Connections between Bounded Query Classes and Non-Uniform Complexity (Long Version)
Amihood Amir, Richard Beigel, William I. Gasarch · 2000
Abstract Let A(x) be the characteristic function of A. Consider the function Fk (x1, . . . , xk) = A(x1) · · ·A(xk). We show that if Fk can be computed with fewer than k queries to some set X then A ∈ P/poly. A generalization of this result has applications to bounded query classes, circuits, and enumerability. In particular we obtain the following. (1) Assuming Σp3 6= Π p 3, 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(log n). (2) If Fk , 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 nO(k)s(n) and depth d(n) +O(1). (3) Assuming that PH 6= Σp4 ∩Π p 4, and < 1, #SAT is not 2 n -enumerable.