«Abstract The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m 1 is an arbitrary ...»
Non-Uniform ACC Circuit Lower Bounds
IBM Almaden Research Center
November 23, 2010
The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR,
NOT, and MODm gates, where m 1 is an arbitrary constant. We prove:
• NTIME[2n ] does not have non-uniform ACC circuits of polynomial size. The size lower bound
can be slightly strengthened to quasi-polynomials and other less natural functions.
• ENP, the class of languages recognized in 2O(n) time with an NP oracle, doesn’t have non-uniform o(1) ACC circuits of 2n size. The lower bound gives an exponential size-depth tradeoff: for every d δ there is a δ 0 such that ENP doesn’t have depth-d ACC circuits of size 2n.
Previously, it was not known whether EXPNP had depth-3 polynomial size circuits made out of only MOD6 gates. The high-level strategy is to design faster algorithms for the circuit satisﬁability problem over ACC circuits, then prove that such algorithms entail the above lower bounds. The algorithm combines known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a subtle strengthening of the author’s prior work [STOC’10].
∗ Supported by the Josef Raviv Memorial Fellowship.
1 Introduction Non-uniform computation allows the size of a program to grow with the sizes of inputs. A non-uniform computation can be naturally represented as an inﬁnite family of Boolean circuits, one for each possible input length. A longstanding aim of complexity theory is to understand the power of non-uniform computation in relation to the usual uniform models which have ﬁxed-size programs. One complication is that non-uniform computations can recognize undecidable languages by having a large enough circuit for each input length. Finding uniform computations that cannot be simulated by small non-uniform circuit families is an extremely difﬁcult venture that is related to other major problems. For instance, P = NP follows if one could provide an NP problem that cannot be solved by any circuit family where the size of the nth circuit is at most polynomial in n. Non-uniform lower bounds establish impossibility results for computation in the physical world: it could be that P = NP, yet NP-complete problems can still be efﬁciently solved using a “bloated” program with sufﬁciently many lines of code. Non-uniform circuit size lower bounds for NP would rule outthis possibility. (However, it is currently possible that all of NP has circuits of size 6n.) In the early 1980’s, researchers began to carefully study the power of non-uniform low depth circuits.
Intuitively, such circuits correspond to extremely fast parallel computations. The initial hope was that if some functions in NP were proved to require large, restricted circuit families, then by gradually lifting the restrictions over time, superpolynomial size unrestricted lower bounds for NP could be attained, proving P = NP. Furst, Saxe, and Sipser [FSS81] and independently Ajtai [Ajt83] showed that functions such as the parity of n bits cannot be computed by polynomial size AC0 circuits, i.e., polynomial size circuit families of constant depth over the usual basis of AND, OR, and NOT gates, where each AND and OR may have arbitrarily many inputs. Yao [Yao85] improved the lower bounds to exponential size, and H˚ stad [H˚ s86] a a proved essentially optimal AC0 lower bounds for parity. Around the same time, Razborov [Raz85] proved superpolynomial lower bounds for solving clique with monotone circuits (i.e., general circuits without NOT gates), and the bound was improved to exponential size by Alon and Boppana [AB87]. However, it was later shown [Raz89] that the monotone techniques probably would not extend to general circuits.
Encouraged by the progress on AC0, attention turned to lower bounds for what seemed to be minor generalizations. The most natural generalization was to grant AC0 the parity function for free. Razborov [Raz87] proved an exponential lower bound for computing the majority of n bits with constant-depth circuits made up of AND, OR, NOT, and MOD2 gates. (A MODm gate outputs 1 iff m divides the sum of its inputs.) Then Smolensky [Smo87] proved exponential lower bounds for computing MODq with constant-depth circuits made up of AND, OR, NOT, and MODp gates, for distinct primes p and q. Barrington [Bar89] suggested the next step would be to prove lower bounds for the class ACC, which consists of constant-depth circuit families over the basis AND, OR, NOT, and MODm for arbitrary constant m 1.1 It is here that progress on strong lower bounds began to falter (although there has been progress on further restricted cases, cf. the Preliminaries). While it was conjectured that the majority of n bits cannot have polynomial ACC circuits, strong ACC lower bounds remained elusive.
After some years of failing to prove a superpolynomial lower bound, the primary questions were weakened. Rather than trying to ﬁnd simple functions that cannot be computed with weak circuits, perhaps we could rule out weak circuits for complicated functions. Could one prove that nondeterministic exponential time (NEXP) doesn’t have polynomial size circuits? A series of papers starting with Babai, Fortnow, Nisan, and Wigderson [BFNW93, KvM99, IKW02] showed that even this sort of lower bound would imply derandomization results: in the case of NEXP lower bounds, it would imply that Merlin-Arthur games can The class is also called ACC0 in the literature. However, as ACCi is hardly studied at all, for any i 0, at the present time it
makes sense to drop the superscript.
be non-trivially simulated with nondeterministic algorithms. This indicated that proving good circuit lower bounds for NEXP would already require signiﬁcantly new ideas.
In this paper, we address two frontier questions concerning non-uniform circuit complexity:
1. Does nondeterministic 2O(n) time have non-uniform polynomial size ACC circuits?
(Is NTIME[2O(n) ] in non-uniform ACC?)
2. Does exponential time with an NP oracle have non-uniform polynomial size circuits?
(Is EXPNP ⊆ P/poly?) Over the years, these questions have turned into notorious and somewhat embarrassing open problems, because it seems so obvious that the answers should be no. It was open if EXPNP could be recognized with depth-3 polynomial size circuits made out of only MOD6 gates.2 We make headway on these frontiers, giving a strong no answer to the ﬁrst question.
Theorem 1.1 NTIME[2n ] does not have non-uniform ACC circuits of polynomial size.
Stronger size lower bounds hold (e.g. quasi-polynomial size) but the results are not very clean; see Section 5.1 for details. For EXPNP, we can prove an exponential lower bound.
Recall that the lowest complexity class for which we know exponential (unrestricted) circuit lower bounds is ∆EXP, the third level of the exponential hierarchy [MVW99].
Extending the approach of this paper to settle the second frontier question may be difﬁcult, but this prospect does not look as implausible as it did before. If polynomial unrestricted circuits could be simulated by subexponential ACC circuits, or if one could improve just a little on the running time of algorithms for the circuit satisﬁability problem, the second question would be settled.
1.1 An Overview of the Proofs Let us sketch how these new lower bounds are proved, giving a roadmap for the rest of the paper. In recent work [Wil10], the author suggested a research program for proving non-uniform circuit lower bounds for NEXP. It was shown that for many circuit classes C, sufﬁciently faster satisﬁability algorithms for Ccircuits would entail non-uniform lower bounds for C-circuits. The objective of this paper is to carry out the proposed research program in the case of ACC circuits.
The proof of the lower bound for ENP (Theorem 1.2) is a combination of complexity-theoretic ideas (time hierarchies, compression by circuits, the local checkability of computation) and algorithmic ideas (fast matrix multiplication, dynamic programming, table lookup).
1. First, we show that satisﬁability algorithms for subexponential size n-input ACC circuits with running time O(2n /nk ) imply exponential size ACC lower bounds for ENP (Theorem 3.2), where k is sufﬁciently large. The model of computation for the satisﬁability algorithm is ﬂexible; we may assume the multitape Turing model or a random access machine. This step considerably strengthens results of earlier work [Wil10] which could only show that an o(2n/3 ) time algorithm for ACC circuit satisﬁability implies lower bounds.
Note that slightly larger classes such as MAEXP and NEXPNP are known to not have polynomial size circuits; see the Prelim
The strategy is to prove that, if there is a faster algorithm for ACC circuit satisﬁability, and there are subexpoo(1) nential (2n ) size ACC circuits for ENP, then every L ∈ NTIME[2n ] can be accepted by a nondeterministic algorithm in O(2n n10 /nk ) time. (Here, 10 is a substitute for a small universal constant.) When k 10 this contradicts the nondeterministic time hierarchy theorem [SFM78, Zak83], so one of the assumptions must be false. The nondeterministic time hierarchy is fairly robust with respect to the machine model: for large enough k, NTIMET M [2n ] ⊆ NTIMERAM [2n /nk ] where NTIMET M denotes nondeterministic multitape Turing machines and NTIMERAM denotes nondeterministic RAMs in the usual logarithmic cost model (cf.
This implies it sufﬁces for the underlying ACC SAT algorithm to work on a RAM (provided it runs in O(2n /nk ) time for large enough k).
Two known facts are required in the proof. First, there is a polynomial-time reduction from any L ∈ NTIME[2n ] to the NEXP-complete problem SUCCINCT 3SAT such that every instance x of length n (for sufﬁciently large n) is reduced to a (unrestricted, not ACC) circuit Cx of size O(n5 ) with at most n + 5 log n inputs (Fact 3.1). That is, the bit string obtained by evaluating Cx on its O(2n n5 ) possible assignments (in lex order) encodes a 3CNF formula FCx that is satisﬁable iff x ∈ L. Second, if ENP is in subexponential ACC, then (given an input x) the lexicographically ﬁrst satisfying assignment to the formula encoded by Cx can be described by an ACC circuit W of subexponential size (Fact 3.2). That is, the bit string obtained by evaluating W on all possible assignments encodes a satisfying assignment to the exponentially long FCx.
If Cx were an ACC circuit, then any L could be simulated in O(2n n5 /nk ) nondeterministic time, by nondeterministically guessing a subexponential ACC circuit W and constructing an ACC circuit satisﬁability instance D built of Cx and W, where D is satisﬁable if and only if W does not encode a satisfying assignment to FCx (as shown in the author’s prior paper). The circuit D has at most n + 5 log n inputs and o(1) 2n size, so the assumed ACC satisﬁability algorithm can handle D in O(2n n5 /nk ) time.
The above argument doesn’t quite work, because we do not know how to produce a Cx that is an ACC circuit (indeed, it may not be possible). An ACC SAT algorithm will not work on D, because it contains a copy of an unrestricted Cx. However, assuming only P has subexponential ACC circuits, we show how to guess and verify an equivalent ACC circuit Cx in nondeterministic O(2n n10 /nk ) time using a faster ACC satisﬁability algorithm (Lemma 3.1). This new result makes it possible to prove lower bounds even with weak ACC satisﬁability algorithms. Furthermore, this part of the proof does not use any speciﬁc properties of ACC, so it could potentially be applied for stronger lower bounds in the future.
2. Next we show how satisﬁability of subexponential ACC circuits of depth d and n inputs can be δ determined in 2n−Ω(n ) time, for a δ 0 that depends on d (Theorem 4.1). Given any such circuit C, δ replace it with C which is an OR of 2n copies of C, where the ﬁrst nδ inputs of each copy are substituted δ with a variable assignment. This ACC circuit C has n − nδ inputs, 2O(n ) size, and C is satisﬁable if and only if C is. Applying a powerful result of Yao, Beigel-Tarui, and Allender-Gore (Lemma 4.1), C can be δ2O(d) replaced by an equivalent depth-2 circuit C of 2n size, which consists of an efﬁciently computable 1/2O(d), and using a nearly symmetric function at the output gate and AND gates below it. Setting δ optimal rectangular matrix multiplication algorithm due to Coppersmith (Lemma 4.3), C can be evaluated δ on all of its possible assignments in 2n−n poly(n) time (Lemma 4.2). Alternatively, this evaluation of C can also be done via simple dynamic programming. This concludes the sketch of the ENP lower bound.
The only use of the full assumption “ENP has ACC circuits” is in Fact 3.2. The lower bound for NEXP (Theorem 1.1) applies the result (which follows from work of Impagliazzo, Kabanets, and Wigderson [IKW02]) that if NEXP has polynomial size (unrestricted) circuits then satisﬁable instances of SUCCINCT 3SAT already have polynomial size (unrestricted) circuits W encoding satisfying assignments (Theorem 5.1). But if P has ACC circuits, it is easy to see that these unrestricted circuits must have equivalent ACC circuits as well (Lemma 5.1). This helps extend the ENP lower bound to NEXP. However, the resulting size lower bound is not exponential: from S(n)-size circuits for NEXP one only obtains S(S(S(n)c )c )c -size ACC circuits encoding satisfying assignments. This allows for some “half-exponential” type improvements in the size lower bounds against NEXP.
Perhaps the most interesting aspect of the proofs is that only the satisﬁability algorithm for ACC circuits relies on speciﬁc properties of ACC. Improved exponential algorithms for satisﬁability are the only barrier to further progress on circuit lower bounds for NEXP. In general, this paper weakens the algorithmic assumptions necessary to prove lower bounds, and strengthens the lower bounds obtained. Let C be a class of circuit families that is closed under composition (the composition of two circuit families from C is also a family in C) and contains AC0. Possible C include constant-depth threshold circuits, Boolean formulas, and unrestricted Boolean circuits. The arguments of Section 3 and Section 5 imply the following metatheorem.