betaFeedback

WorksComputer Science

Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting

Abstract

We study circuit lower bounds for extended gate bases using exact CNF counting and an extension-ring form of the contraction theorem of OpenAI. The deterministic counting theorem of Claude (Anthropic) yields an ENP\mathsf{E}^{\mathsf{NP}} language requiring Ω(mlog⁡m/log⁡log⁡m)Ω(m\sqrt{\log m}/\log\log m) gates over unbounded AND/OR with binary XOR, infinitely often. Using that contraction theorem, a bounded binary base with a linear budget of arbitrary XOR and symmetric gates requires Ω(mlog⁡m)Ω(m\sqrt{\log m}) gates infinitely often. These results extend the binary-gate lower bound of OpenAI. Signed long-clause selectors reduce the first counting problem to the difference of two ordinary 3-CNF counts. Affine characters and unit-separated interpolation give the second counting interface, with logarithmic cost per symmetric-gate arity. A quantitative local-reduction transfer accounts for auxiliary variables, branch counts, and integer recovery.

Introduction

Problem and motivation

Faster circuit counting can yield lower bounds for explicit languages through the algorithm-to-lower-bound paradigm. Extending the gate basis changes the cost of verifying a guessed witness circuit. Long defining clauses and high-arity symmetric relations must be represented without exhausting the quantitative saving of the counter.

Main results

Let U\mathcal{U} consist of arbitrary-fan-in AND/OR, binary XOR, and unary NOT/COPY gates, with signed edges and constants allowed. Size counts noninput gates. The first result uses the exact CNF counting theorem of Claude (Anthropic), stated as Theorem 3.

Theorem 1. There are a language W∈ENPW \in E^{\mathrm{NP}} and c>0c > 0 such that, at infinitely many input lengths mm, every U\mathcal{U} circuit computing WW has more than

cmlog⁡mlog⁡log⁡mcm\frac{\sqrt{\log m}}{\log\log m}

noninput gates. No depth restriction is imposed.

Source / taskBound and scope
OpenAI [5 Corollary 1.4 and Appendix C.1]Binary gates: Ω(mlog⁡m)\Omega(m\sqrt{\log m}) infinitely often in ENP\mathrm{E}^{\mathrm{NP}}.
Theorem 1Unbounded AND/OR and binary XOR: Ω(mlog⁡m/log⁡log⁡m)\Omega(m\sqrt{\log m}/\log\log m) infinitely often.
Theorem 2Binary base with b(C)≤δmb(C) \le\delta m: Ω(mlog⁡m)\Omega(m\sqrt{\log m}) infinitely often, using the extension-ring form of D.1.

Table 1. Gate models and quantitative lower bounds. The gain is the extended basis supported by each counting interface.

For the second model, ordinary binary gates are supplemented by arbitrary-fan-in XOR and other symmetric gates. Define b(C)b(C) by charging one per designated XOR gate and log⁡2(dj+1)\log_2(d_j+1) per other designated symmetric gate of arity djd_j. Binary gates count toward size and have zero exceptional budget. Gate lists contain no duplicate signed wires; depth and fanout are unrestricted.

Theorem 2. Using the contraction theorem of OpenAI as extended in Theorem 4, there are constants δ,c>0\delta, c > 0 and a language W∈ENPW \in\mathrm{E}^{\mathrm{NP}} such that, for infinitely many input lengths mm, every circuit for WW with b(C)≤δmb(C) \le\delta m has at least cmlog⁡mc m\sqrt{\log m} gates. Depth and fanout are unrestricted. Consequently, for a sufficiently small fixed ϵ>0\epsilon> 0, the same lower bound allows simultaneously ⌊ϵm⌋\lfloor\epsilon m\rfloor arbitrary-fan-in XOR gates and ⌊ϵm/log⁡2(m+2)⌋\lfloor\epsilon m/\log_2(m+2)\rfloor other arbitrary symmetric gates, with all remaining gates bounded binary.

Technical overview

The proof follows the algorithm-to-lower-bound paradigm: a sufficiently fast exact counter can verify a succinctly represented satisfying assignment faster than a nondeterministic time hierarchy permits. Extending the circuit basis changes the verifier’s gate relations. The central task is to count the resulting assignments while charging every auxiliary variable, algebraic branch, and recovery operation. The transfer theorem separates this task from the hierarchy argument, and the two counting interfaces instantiate it with different costs.

The transfer starts with a hard unary language. A local reduction represents a computation on unary input 1n1^n by a 3-CNF whose clauses can be decoded using O(n)O(n) binary gates. The bits of its first satisfying assignment define a language in ENP\mathrm{E}^{\mathrm{NP}}. If that language had small circuits at every sufficiently large relevant length, a verifier could guess one such circuit, make three copies, and count the clause addresses it violates. A zero count certifies satisfaction. The general transfer theorem takes the full counting time as its input, including an additive branch budget in the exponent, and chooses constants so that the resulting verifier contradicts the hierarchy.

The first interface preserves the variable budget. An arbitrary-fan-in AND or OR gate has one long defining clause and many short implication clauses. Replacing its long clause by a chain of bounded-width clauses would charge variables to its fan-in. A signed selector instead represents the long-clause indicator as a sum of weights: the selector value one has weight −1-1 and forces every literal false. Summing over that selector gives one when the clause is true and zero otherwise. Each long clause thus contributes one selector. Binary XOR gates already have constant-size 3-CNF definitions.

Two ordinary counts recover the signed count. A unique-extension XOR chain records the parity of all negative-weight selectors. Its even and odd cases give two ordinary 3-CNFs, and their model-count difference equals the required circuit count. For nn inputs and gg gates, each formula has at most n+3gn+3g variables; its clauses are polynomial in the full circuit description. The variable-dependent term of Anthropic’s counting theorem [2] therefore applies at arbitrary clause density. This gives the counter used for unbounded AND/OR with binary XOR, and the transfer yields an Ω(mlog⁡m/log⁡log⁡m)\Omega(m\sqrt{\log m}/\log\log m) lower bound.

The second interface pays a logarithmic cost per symmetric gate. An ordinary bounded-fan-in encoding of a high-arity symmetric gate computes its input Hamming weight and then evaluates a truth table. That representation charges auxiliary gates to the arity. The intended budget instead charges log⁡2(dj+1)\log_2(d_j + 1) for a gate of arity djd_j. Unit-separated interpolation achieves this budget by expressing its truth table as a sum of dj+1d_j + 1 products of unary weights. Selecting one summand per gate gives ∏j(dj+1)\prod_j(d_j + 1) branches. Each branch has the original bounded-arity constraints and accumulated unary weights, so its network size is independent of those symmetric input lists except through polynomial-time weight accumulation.

Affine characters handle arbitrary-fan-in XOR. An affine subsystem of rank rr has an exact character expansion with 2r2^r terms. Each term contributes unary signs, and the complete sum is 2r2^r times the desired count. Evaluating modulo 2N+r+12^{N+r+1} retains the whole numerator when there are NN Boolean variables. The algorithm takes the canonical integer residue and divides by 2r2^r. This treats long XOR relations without adding a chain proportional to their input occurrences. The total branch exponent is r+∑jlog⁡2(dj+1)r + \sum_j \log_2(d_j + 1).

Extension-ring arithmetic supports the weighted branches. The interpolation coefficients live in a finite unramified extension of Z/2pZ\mathbb{Z}/2^p\mathbb{Z}, where residue-distinct points have unit differences. The contraction theorem used here follows the proof of OpenAI’s Theorem D.1 [5] over that coefficient ring. If the input residue field is too small for its interpolation grid, a tower extension provides enough points with logarithmic total degree. Appendix A checks the ring arithmetic, coordinatewise precision, recursion identity, and recovery of the original coordinates. This supplies a deterministic polynomial-space counter with time 2B+r+O(s/log⁡s)2^{B+r+O(s/\sqrt{\log s})} up to polynomial factors.

The lower bounds are the final compositions. The first counter enters the transfer with the slowly growing denominator log⁡s/log⁡log⁡s\sqrt{\log s}/\log\log s. The second enters with log⁡s\sqrt{\log s} and a branch budget linear in the witness input length. Three witness copies multiply that budget by at most three. The same transfer theorem then gives the two stated lower bounds, with their gate models and budgets carried explicitly. Figure 1 displays this common argument and the distinct counting inputs.

Flowchart showing local decoder and guessed witness circuit; signed clauses to two 3-CNF counts; affine characters and unit interpolation to weighted contractions; full counting-time bounds to quantitative transfer; and hierarchy contradiction to the two circuit lower bounds

Figure 1. Two counting interfaces feed the same quantitative transfer theorem.

Related work

Williams [7] develops the algorithm-to-lower-bound connection; Jahanjou–Miles–Viola [3] give the local reductions used in its quantitative form. The bounded-binary transfer with the present counting exponents appears in [5 Appendix C.1]. The circuit results here extend its gate interfaces. Signed large-clause reductions are developed in [4, 1]. Tamaki [6] gives counting algorithms and ENPE^{\mathrm{NP}} lower bounds for depth-two circuits with symmetric and threshold gates; our symmetric-gate statement allows arbitrary depth under the stated exceptional-gate budget. Claude (Anthropic) [2 Theorem 1] proves the counting bound used in our first interface. Its clause-dependent term also gives 2O(N/log⁡N)2^{O(N/\sqrt{\log N})} time for fixed-width CNFs with O(N)O(N) clauses. The corresponding exact-counting statement is formalized in Lean 4 [2 Appendix E].

Organization

Section 2 states the external counting theorem and the extension-ring contraction theorem. Section 3 proves the common quantitative transfer. Sections 4 and 5 construct the two counters. Section 6 composes them with the transfer to prove the main results. Appendix A derives the coefficient-ring extension from the proof of D.1.

Preliminaries and counting theorems

All circuits are acyclic, and size counts noninput gates. The full input description length includes gate input lists and symmetric truth tables. Logarithms in counting exponents are base two; ln⁡\ln is the natural logarithm. We use ENP=DTIME(2O(m))NP\mathrm{E}^{\mathrm{NP}} = \mathrm{DTIME}(2^{O(m)})^{\mathrm{NP}}.

Theorem 3 (Claude (Anthropic), Theorem 1 [2]). There are one deterministic finite-alphabet multi-stack Turing machine and one absolute constant CC such that, for every k≥1k \ge1, every N≥4N \ge4, and every kk-CNF in which all NN variables occur, with M≥2M \ge2 distinct clauses, the machine computes its exact model count in at most

2Cmin⁡{k2Nlog⁡2log⁡2Nlog⁡2N,kMlog⁡2M}(1)2^{C \min\left\{ \frac{k^2 N \log_2 \log_2 N}{\sqrt{\log_2 N}}, \frac{kM}{\sqrt{\log_2 M}} \right\}} \tag*{(1)}

steps, up to integer rounding of the time bound.

The cited Theorem 1 appears on pages 1–2 of [2]; Appendix E specifies the Lean statement and its machine model. A fixed multi-stack machine has a constant-overhead simulation by a fixed multitape machine. Repeated clauses can be removed in input-polynomial time. Unused variables contribute a power of two to the count, and inputs with N<4N < 4 or M<2M < 2 are counted directly. For k=3k = 3 the variable term of (1) gives 2O(Nlog⁡log⁡N/log⁡N)2^{O(N \log\log N/\sqrt{\log N})} time at arbitrary clause density. For fixed kk and M≤DNM \le DN, the clause term gives 2Ok,D(N/log⁡N)2^{O_{k,D}(N/\sqrt{\log N})} time. These consequences use the absolute constant in Theorem 3.

For the second interface, let

Rp=(Z/2pZ)[U]/(f(U)),R_p = (\mathbb{Z}/2^p\mathbb{Z})[U]/(f(U)),

where ff is a monic binary lift of an irreducible polynomial of degree ee over F2\mathbb{F}_2.

Theorem 4 (Extension-ring form of the contraction theorem of OpenAI). A bipartite Boolean tensor network with O(s)O(s) wires, polynomially many vertices, maximum degree at most ⌈s9/10⌉\lceil s^{9/10}\rceil, and description length L\mathcal{L} can be contracted over RpR_p in deterministic time

(s+L)O(1)2O(s/log⁡(s+2))(s + \mathcal{L})^{O(1)} 2^{O\left(s/\sqrt{\log(s+2)}\right)}

and polynomial space, for p=O(s)p = O(s) and e=O(log⁡(s+L))e = O(\log(s+\mathcal{L})), when each local entry is computable in (s+L)O(1)2O(s9/10)(s+\mathcal{L})^{O(1)}2^{O(s^{9/10})} time and polynomial space. The constants depend on the fixed bounds in these assumptions.

The statement follows from the contraction argument in OpenAI [5 Appendix D.4]. Appendix A gives the coefficient-ring extension, precision analysis, and recovery of the original coordinates.

A quantitative local-reduction transfer

The transfer is parameterized by the complete test-time bound T(U,R)=poly⁡(n)2R+AU/a(U)T(U,R) = \operatorname{poly}(n)2^{R+AU/a(U)}. The function aa measures the counting speedup and RR is the branch exponent. The transfer uses the unary nondeterministic hierarchy stated in Williams, Theorem 2.1 of the full version [7], and Jahanjou–Miles–Viola, Theorem 1 [3]. The bounded-binary combination appears in [5 Appendix C.1].

Lemma 5 (Uniform linear-size clause decoder). There is a fixed unary language

H0∈NTIME(2n)∖NTIME(2n/2)H_0 \in\mathrm{NTIME}(2^n) \setminus\mathrm{NTIME}(2^{n/2})

and a polynomial-time construction of a decoder with O(n)O(n) binary gates which maps q=n+O(log⁡n)q = n + O(\log n) bits to the three variable addresses and signs of a 33-CNF Φn\Phi_n. The formula is satisfiable exactly when 1n∈H01^n \in H_0. Its variable addresses can be padded to dndn bits for one fixed integer dd.

Proof. The proof applies the local reduction to a unary hierarchy language and uses the constant support of each decoder output. The hierarchy applies since 2(n+1)/2=o(2n)2^{(n+1)/2} = o(2^n). We simulate the fixed machine with allowance T=2nnO(1)T = 2^n n^{O(1)}. We apply the local reduction with r=2r = 2, giving q=max⁡(log⁡2T,n/2)+O(log⁡n)+O(log⁡log⁡T)q = \max(\log_2 T,n/2)+O(\log n)+O(\log\log T). Each of its O(n)O(n) output bits has a constant-depth decision tree and thus a support of at most a fixed constant ww input bits. The circuit delivered by the reduction can be evaluated in polynomial time. We evaluate it on all strings of Hamming weight at most ww. For any essential coordinate ii, take a pair of inputs differing only at ii on which the output differs. Zeroing all coordinates outside the support preserves that difference and puts both inputs among these queries. Comparing such queried pairs identifies the entire support; the same queries give its truth table. Realizing each constant-size truth table takes O(1)O(1) binary gates. This constructs the linear-size decoder uniformly, even if the initial circuit was larger. Bounded exceptional lengths can be handled separately.

We declare all 2dn2^{dn} variables, including unused addresses. For inputs ii of length dndn, let W(i)W(i) be bit ii of the lexicographically first satisfying assignment of Φn\Phi_n, or zero when none exists. We set W=0W = 0 at all other lengths. The input length determines nn. Writing Φn\Phi_n and querying an NP oracle about successive assignment prefixes takes at most 2dn2^{dn} queries of size 2O(n)2^{O(n)}. Therefore W∈ENPW \in\mathrm{E}^{\mathrm{NP}}.

Theorem 6 (Explicit exponent and budget transfer). Let aa be eventually nondecreasing, tend to infinity, and satisfy a(n)=no(1)a(n)=n^{o(1)}, a(cna(n))/a(n)→1a(cna(n))/a(n)\to1 for every constant c>0c>0, and a(dn)/a(n)→1a(dn)/a(n)\to1 for fixed d>0d>0. Suppose a circuit model has polynomial description length for circuits with n1+o(1)n^{1+o(1)} gates, includes binary gates, and admits the following deterministic test for a guessed witness circuit CC of ss gates on dndn bits. Form three copies with the decoder of Lemma 5 and count violating clause addresses. Suppose this test has a deterministic multitape implementation taking time at most

poly⁡(n)2R+AU/a(U),U=κs+Bn,R≤bδdn,\operatorname{poly}(n)2^{R+AU/a(U)}, \qquad U=\kappa s+Bn,\qquad R\le b\delta dn,

for fixed positive A,B,κ,bA,B,\kappa,b, whenever the permitted witness budget is at most δdn\delta dn. The exponent bound must include all preprocessing, branches and exact reconstruction. Assume an effective integer threshold sn=(η+o(1))na(n)s_n=(\eta+o(1))na(n) can be computed in polynomial time. Then for sufficiently small positive δ,c\delta,c, at infinitely many lengths mm every permitted circuit computing WW has more than cma(m)cma(m) gates. For a model without a budget take R=0R=0 and omit δ\delta.

Proof. The proof guesses a small witness circuit and uses the assumed counting time to contradict the unary nondeterministic hierarchy. Choose δ\delta so bδd<1/8b\delta d<1/8 and η\eta so Aκη<1/8A\kappa\eta<1/8. If the conclusion failed, sufficiently small c<η/dc<\eta/d and the fixed-scale regularity of aa would provide witness circuits of at most sns_n gates at every sufficiently large address length dndn. On input 1n1^n, guess such a circuit and form the violation circuit. All guessing, budget checks and decoding use polynomial time. We accept precisely when the number of violated clause addresses is zero. For a satisfiable Φn\Phi_n, its first-witness circuit is an accepting guess. For an unsatisfiable Φn\Phi_n, every guessed circuit describes an assignment violating at least one clause. Soundness holds for every guessed circuit.

Now U=(κη+o(1))na(n)U=(\kappa\eta+o(1))na(n). We squeeze between fixed positive multiples of na(n)na(n); monotonicity and regularity give AU/a(U)=(Aκη+o(1))nAU/a(U)=(A\kappa\eta+o(1))n. The total verifier time is 2(bδd+Aκη+o(1))n2^{(b\delta d+A\kappa\eta+o(1))n}, less than 2n/22^{n/2} for all sufficiently large nn. The stipulated multitape bound includes all workspace access costs. We hardwire the finitely many smaller lengths and reject nonunary inputs. This contradicts the chosen hierarchy language. Thus the bound fails at infinitely many address lengths dndn, which proves the result. □\square

For sufficiently large xx, the two applications use

a0(x)=log⁡2x,a1(x)=log⁡2xlog⁡2log⁡2x.a_0(x)=\sqrt{\log_2 x},\qquad a_1(x)=\frac{\sqrt{\log_2 x}}{\log_2\log_2 x}.

Their regularity follows from log⁡(cnai(n))=log⁡n+O(log⁡log⁡n)\log(cna_i(n))=\log n+O(\log\log n). For a0a_0 take

sn=⌊ηn⌊⌊log⁡2n⌋⌋⌋.s_n=\left\lfloor\eta n\left\lfloor\sqrt{\left\lfloor\log_2 n\right\rfloor}\right\rfloor\right\rfloor.

For a1a_1, divide the inner expression by ⌊log⁡2⌊log⁡2n⌋⌋\left\lfloor\log_2\left\lfloor\log_2 n\right\rfloor\right\rfloor before the outer floor. These thresholds use integer arithmetic and have the required asymptotics.

Witness modelCounting cost on the violation instanceConsequence
Unbounded AND/OR; binary XORR=0R=0, U=9s+Ω(n)U=9s+\mathit{\Omega}(n), a=a1a=a_1Ω(mlog⁡m/log⁡log⁡m)\mathit{\Omega}(m\sqrt{\log m}/\log\log m) gates
Binary base; budgeted arbitrary XOR and other symmetric gatesR≤3δdnR\leq3\delta dn, U=3s+Ω(n)U=3s+\mathit{\Omega}(n), a=a0a=a_0Ω(mlog⁡m)\mathit{\Omega}(m\sqrt{\log m}) gates under the budget

Table 2.

Counting algorithm I: signed long clauses

This counter preserves a linear variable budget by replacing each long defining clause with one signed selector. An auxiliary parity chain converts the resulting signed sum into two ordinary 3-CNF counts. Lemma 7 supplies the complete bound needed for the transfer.

The circuit class U\mathcal{U} is defined in § 1.2.

Lemma 7. For a circuit in U\mathcal{U} with nn inputs, gg gates and full description length LL, its output-one preimages are the difference of the model counts of two ordinary 3-CNFs, each on at most V=n+g+2H≤n+3gV=n+g+2H\leq n+3g variables and O(L+g)O(L+g) clauses. Here HH is the number of AND/OR gates of fan-in at least three. By Theorem 3, the two counts are computable in time

(L+V)O(1)2O(Vlog⁡log⁡(V+4)/log⁡(V+2)).(L+V)^{O(1)}2^{O\left(V\log\log(V+4)/\sqrt{\log(V+2)}\right)}.

Proof. The proof replaces long defining clauses by signed selectors and separates their total sign with one parity chain. The construction uses one variable per gate. An AND definition uses all (¬z∨li)(\lnot z\lor l_i) and the single clause (z∨⋁i¬li)(z\lor\bigvee_i\lnot l_i); an OR definition uses (z∨¬li)(z\lor\lnot l_i) and (¬z∨⋁ili)(\lnot z\lor\bigvee_i l_i). XOR has four ternary clauses and COPY has two binary clauses. There is a unique gate extension of each input. For a long clause ⋁ili\bigvee_i l_i, replace it with (¬s∨¬li)(\lnot s\lor\lnot l_i) and give s=1s=1 weight −1-1. With all input and gate variables fixed, the selector sum is one for a true clause and zero for a false clause. This is the existing signed-clause construction [4, 1]. A unique-extension XOR chain on the HH selectors uses H−1H-1 further variables. We fix its parity to zero and one to obtain the two formulas; for H=0H=0, use an inconsistent second formula. The count difference is exactly the claimed number.

Each individual count needs at most V+1V+1 bits. After duplicate clauses are removed, let ViV_i be the number of occurring variables of the iith formula, and let MiM_i be its clause count. Theorem 3, with k=3k=3, gives

2Cmin⁡{9Vilog⁡2log⁡2Vilog⁡2Vi,3Milog⁡2Mi}.2^{C\min\left\{9V_i\frac{\log_2\log_2 V_i}{\sqrt{\log_2 V_i}},\frac{3M_i}{\sqrt{\log_2 M_i}}\right\}}.

Restoring the V−ViV-V_i unused variables multiplies its output by 2V−Vi2^{V-V_i}. The first term, Vi≤VV_i\leq V, and polynomial-time normalization give the displayed general-density bound. The cases Vi<4V_i<4 or Mi<2M_i<2 are evaluated directly. ∎

Counting algorithm II: affine characters and unit interpolation

The second counter removes affine relations by characters and arbitrary symmetric gates by a separated interpolation identity. Both transformations produce unary weights. Theorem 8 combines their branch count with the extension-ring contraction theorem and reconstructs the exact integer count.

Exact affine-character removal

The following identity supplies the XOR part of the symmetric-gate counter. On NN Boolean variables, row-reduce Ax=aAx=a over F2\mathbb{F}_2. An inconsistent system contributes zero. Otherwise retain rr independent rows Rx=dRx=d. For every xx,

2r[Rx=d]=∑y∈F2r(−1)y⋅d(−1)(RTy)⋅x.2^r [Rx=d] = \sum_{y\in\mathbb{F}_2^r} (-1)^{y\cdot d}(-1)^{(R^T y)\cdot x}.

This follows by factoring the character sum into rr sums over single bits; a nonzero residual makes one such factor zero. Multiplication by any other constraint product and summation over xx proves the identity for its count. Every character becomes a unary sign on each variable. In a coefficient ring of characteristic 2p2^p, perform all branch sums at precision p=N+r+1p=N+r+1. If the final unscaled count is an integer ZZ with 0≤Z≤2N0\le Z\le2^N, the resulting canonical integer residue is exactly 2rZ<2N+r+12^r Z<2^{N+r+1}. We divide this integer by 2r2^r afterwards. Polynomially many bits suffice, and sequential character enumeration uses polynomial space.

For the mixed decomposition below, individual branches can have extension-ring values. The identity applies before any decomposition, so the complete sum is the integer 2rZ2^rZ. This identity justifies the final reconstruction.

Unit interpolation for symmetric gates

We apply the unit-separated interpolation construction of OpenAI [5 Appendix D.4.1] before contraction. It removes arbitrary symmetric gates from an otherwise bounded-arity circuit and charges their arities through a multiplicative branch count.

Coefficient ring and interpolation points For the explicit input length L\mathcal{L}, choose

e=max⁡{4⌈log⁡2s⌉,⌈log⁡2(dmax⁡+1)⌉,1}.e=\max\{4\lceil\log_2 s\rceil,\lceil\log_2(d_{\max}+1)\rceil,1\}.

where dmax⁡≤Ld_{\max}\le\mathcal{L} is the largest symmetric arity. The irreducible polynomial defining RpR_p can be found in time polynomial in s+Ls+\mathcal{L}, since 2e=O(s4+dmax⁡+1)2^e=O(s^4+d_{\max}+1). Ring operations and unit inversions take polynomial time in e,pe,p. Binary-coordinate representatives give 2e2^e points with pairwise unit differences. Theorem 4 supplies contraction for the resulting RpR_p-valued branches, with this coefficient ring fixed throughout each call.

An integral separated decomposition Let a gate have dd input occurrences, with Boolean truth table f(0),…,f(d)f(0),\ldots,f(d) indexed by input Hamming weight. Its output bit is yy. We choose distinct residue-field lifts α0,…,αd\alpha_0,\ldots,\alpha_d in RpR_p; zero is allowed. The matrix Vt,j=αjtV_{t,j}=\alpha_j^t, 0≤t,j≤d0\le t,j\le d, has determinant ∏i<j(αj−αi)\prod_{i<j}(\alpha_j-\alpha_i), a unit. For each y∈{0,1}y\in\{0,1\} solve

∑j=0dcj,yαjt=[y=f(t)],0≤t≤d.(2)\sum_{j=0}^{d} c_{j,y}\alpha_j^t=[y=f(t)],\qquad0\le t\le d. \tag*{(2)}

These two solves take polynomial time in d,e,pd,e,p and lose no precision. Elimination always has a unit pivot after a row exchange: reduction modulo two is an invertible matrix over a field. Equivalently the coefficients are defined integrally in O\mathcal{O} and reduced modulo 2p2^p.

For any Boolean input occurrences b1,…,bdb_1,\ldots,b_d, the exact identity is

[y=f(∑ibi)]=∑j=0dcj,y∏i=1dαjbiin Rp.(3)[y=f(\sum_i b_i)]=\sum_{j=0}^{d}c_{j,y}\prod_{i=1}^{d}\alpha_j^{b_i}\quad\text{in }R_p. \tag*{(3)}

We use 00=10^0=1. A positive literal on variable xx contributes unary weights (1,αj)(1,\alpha_j), and a negative literal contributes (αj,1)(\alpha_j,1). The output variable receives weights (cj,0,cj,1)(c_{j,0},c_{j,1}). If a variable occurs more than once, multiply all its unary weights. Shared inputs, fanout and negated inputs therefore cause no independence assumption. When the gates have arbitrary depth, an output can receive both its own coefficient weight and factors from later gates; multiplication still applies pointwise.

A complete weighted counting interface

We consider NN Boolean variables, m0m_0 hard predicates of fixed arity, arbitrary explicitly described symmetric gate relations of arities d1,…,dhd_1,\ldots,d_h, and an affine subsystem of rank rr. Let

s=N+m0+2,B=∑j=1hlog⁡2(dj+1).s=N+m_0+2,\qquad B=\sum_{j=1}^{h}\log_2(d_j+1).

Inconsistent affine systems give count zero. Otherwise the exact character identity from Section 5.1 removes the rr independent equations using 2r2^r terms and an eventual integer division by 2r2^r.

Theorem 8. The preceding mixed system has a deterministic exact counting algorithm with time

(s+L)O(1)2B+r+O(s/log⁡(s+2))(4)(s+\mathcal{L})^{O(1)}2^{B+r+O(s/\sqrt{\log(s+2)})} \tag*{(4)}

and polynomial space. Constants depend only on the hard-predicate arity. Recovery and original-assignment unranking use a polynomial number of deterministic counting calls. When the count is positive, exact uniform sampling uses a polynomial number of counting calls and polynomial expected additional time with fair random bits.

Proof. The proof expands the affine and symmetric constraints into unary weights, contracts each branch, and reconstructs one exact integer. The precision is p=N+r+1≤2N+1p = N + r + 1 \le2N + 1. We enumerate one interpolation index for each symmetric gate and one affine character, sequentially. There are exactly 2r∏j(dj+1)=2B+r2^r \prod_j(d_j + 1) = 2^{B+r} branches. A branch has only the fixed-arity hard predicates and a pair of unary weights wv(0),wv(1)∈Rpw_v(0), w_v(1) \in\mathbb{R}_p at each original variable. All these weights can be accumulated in input-polynomial time and space.

We make the fixed-density network of source D.2: one tensor per hard predicate, equality trees for its variable occurrences, and the unary weights attached at one port of each variable. A variable with no hard occurrences contributes wv(0)+wv(1)w_v(0) + w_v(1) as a scalar. There are O(s)O(s) wires, bounded maximum degree, and polynomial-time local entries. Subdivision makes the graph bipartite without changing its contraction. Theorem 4 evaluates the branch in the structural time in (4), with polynomial space. Each symmetric input occurrence contributes to an accumulated unary weight.

We sum all branch residues with their affine-character signs. By the two pointwise identities the result is the constant-coordinate integer 2rZ2^r Z modulo 2N+r+12^{N+r+1}, where 0≤Z≤2N0 \le Z \le2^N is the required count. All other coordinates vanish. The canonical constant residue is the actual numerator, so divide it by 2r2^r as an integer. In the absence of affine equations p=N+1p = N + 1 suffices, regardless of the symmetric arities.

We pin original variables successively with unary hard predicates. The resulting instances have NN variables, the same symmetric decompositions and affine rank bound, and at most NN additional hard predicates. The child counts sum to their parent’s count. The usual count self-reduction recovers a solution and maps each integer in [0,Z)[0, Z) bijectively to one solution. For exact uniform sampling when Z>1Z > 1, let b=⌈log⁡2Z⌉b = \lceil\log_2 Z \rceil. A trial draws bb independent fair bits, interprets them as an integer a∈[0,2b)a \in[0, 2^b), and accepts precisely when a<Za < Z. The accepted index is uniform on [0,Z)[0, Z), and the acceptance probability Z/2b>1/2Z/2^b > 1/2 gives fewer than two trials in expectation. For Z=1Z = 1, the index is zero. Unranking the accepted index therefore yields an exact uniform solution with O(log⁡(Z+1))O(\log(Z + 1)) expected additional time. We stream all branch choices and keep one accumulator, proving the space bound.

For an acyclic circuit with nn inputs and gg gates, give every gate one output variable, so N=n+gN = n + g. Every bounded binary gate imposes one arity-three predicate. We remove selected arbitrary-fan-in XOR gates by characters and all other designated symmetric gates by (3); pin the requested output. Then m0=O(N)m_0 = O(N) and (4) becomes

poly⁡(L+N)2B+r+O(N/log⁡(N+2)).\operatorname{poly}(\mathcal{L} + N)2^{B+r+O(N/\sqrt{\log(N+2)})}.

Each input has a unique full gate assignment, so the answer counts original input preimages. For example, B+r=O(N/log⁡N)B + r = O(N/\sqrt{\log N}) preserves the fixed-density exponent, while B+r=o(N)B + r = o(N) gives subexponential time in NN. These statements have no depth or fanout restriction. They include majority and exact-Hamming-weight gates.

Proofs of the circuit lower bounds

Both conclusions follow from Theorem 6. The first proof substitutes the two-CNF counter with denominator a1a_1; the second substitutes the weighted counter with denominator a0a_0 and the explicit exceptional-gate budget. The witness language is the one constructed in § 3.

Unbounded AND/OR and binary XOR

Proof of Theorem 1. We apply Theorem 6 with a=a1a=a_1 and no budget. A witness circuit with ss gates on dndn bits has three copies in the violation circuit, along with the O(n)O(n)-gate binary decoder. There are q=n+O(log⁡n)q=n+O(\log n) inputs, at most 3s+B0n3s+B_0n gates and at most 3s+13s+1 long defining clauses. Lemma 7 therefore yields two 3-CNFs on at most 9s+Bn9s+Bn variables. Each has polynomially many clauses: duplicate equal literals can be removed from AND/OR gates, so a complete witness description has length O(s(dn+s)log⁡(dn+s+2))O(s(dn+s)\log(dn+s+2)). The three-copy decoder, output pin and parity definitions add only polynomial description length. The complete verifier time is

poly⁡(n)2AU/a1(U),U=9s+Bn.\operatorname{poly}(n)2^{AU/a_1(U)}, \qquad U=9s+Bn.

One may pad both formulas with the same number of unused variables; this multiplies both counts by the same power of two and preserves zero difference. The exact difference is the nonnegative number of violated clause addresses, so the transfer’s completeness and soundness apply. For example, any sufficiently small rational η<1/(72A)\eta<1/(72A) meets its time requirement. The two calls run sequentially; the final subtraction uses O(U)O(U) bits.

A quantitative larger-basis circuit lower bound

We use the standard convention that a gate input list contains no duplicate signed wires, so dj≤2(m+g)d_j\leq2(m+g) on mm inputs and gg gates. Explicitly repeated lists use their actual BB in the counting algorithm. We give arbitrary-fan-in XOR gates unit budget cost and all other designated symmetric gates cost log⁡2(dj+1)\log_2(d_j+1). Let b(C)b(C) be the sum of these costs; ordinary binary gates are free in this budget but still count toward gg.

Proof of Theorem 2. We use Theorem 6 with a=a0a=a_0. A witness circuit on dndn bits with ss gates and b(C)≤δdnb(C)\leq\delta dn produces a violation circuit with N≤3s+B0nN\leq3s+B_0n input and gate variables. The decoder, sign checks and final AND use bounded binary gates. The three copies have combined removed cost B+r≤3δdnB+r\leq3\delta dn: the affine rank is at most the number of removed XOR rows. Thus Theorem 8, with fixed-density hard gates, gives poly⁡(n)23δdn+AU/a0(U)\operatorname{poly}(n)2^{3\delta dn+AU/a_0(U)} for U=3s+B1nU=3s+B_1n. The coefficient of the budget term is exactly one; it is the binary logarithm of the explicit branch count.

Every witness gate has a polynomial-size input list and, for a symmetric gate, a table of dj+1d_j+1 bits. After substitution of decoded addresses, occurrences that coincide are retained. The counter already supports repeated inputs with the original witness budget. Polynomial space gives a multitape simulation with polynomial overhead. The transfer theorem applies with 3δd<1/83\delta d < 1/8 and 3Aη<1/83A\eta< 1/8. The constants are independent of the gate arities.

For its final consequence it suffices to consider g<cmlog⁡mg < cm\sqrt{\log m}, since larger circuits already meet the conclusion. For all sufficiently large mm, log⁡2(2(m+g)+1)≤2log⁡2(m+2)\log_2(2(m+g)+1) \le2\log_2(m+2). The stated gate allowances therefore have budget at most ϵm+2ϵm=3ϵm\epsilon m + 2\epsilon m = 3\epsilon m. We take 3ϵ≤δ3\epsilon\le\delta.

Discussion and open problems

The two lower bounds extend the binary-gate conclusion of OpenAI [5 Corollary 1.4 and Appendix C.1] through distinct counting interfaces. Signed selectors preserve a linear variable budget for arbitrary-fan-in AND/OR gates. Affine characters and unit-separated interpolation preserve a linear wire budget after the symmetric gates have been expanded, with the expansion charged by B+rB+r.

An ordinary bounded-fan-in encoding of a symmetric gate of arity dd computes its Hamming weight with O(dlog⁡(d+2))O(d\log(d+2)) auxiliary gates and evaluates its explicit truth table with O(d)O(d) further gates. Across all exceptional gates this gives a CNF size controlled by N+∑jdjlog⁡(dj+2)N+\sum_j d_j\log(d_j+2), whereas the theorem budgets ∑jlog⁡2(dj+1)\sum_j\log_2(d_j+1). A CNF counting reduction with the latter budget would give a counting-theorem basis for the symmetric-gate bound. The present proof uses Theorem 4 for its extension-ring branches.

Two further questions are whether the logarithmic loss in the unbounded AND/OR lower bound can be removed, and whether a larger exceptional-gate budget permits the square-root-logarithmic lower bound.

AI assistance

OpenAI Codex was used to assist with drafting and revising the manuscript, developing parts of the mathematical arguments, and checking derivations.

  1. OpenAI: The Exponential Time Hypothesis is False. OpenAI Math Release preprint (2026), https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 25 October 2026

  1. Tamaki, S.: A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates (2016), https://eccc.weizmann.ac.il/report/2016/100/, ECCC TR16-100

  1. Williams, R.: Improving Exhaustive Search Implies Superpolynomial Lower Bounds (2013). https://doi.org/10.1137/10080703X, https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf, SIAM Journal on Computing 42(3), 1218–1244

Extension-ring contraction from the proof of Theorem D.1

Proof of Theorem 4. The idea is to run the contraction recursion of OpenAI [5 Appendix D.4] over an unramified coefficient algebra containing the input ring. The Boolean network and all recursion parameters are kept fixed. The following construction gives the coefficient algebra and checks the places where that proof uses its ring.

A coefficient algebra containing the input. Let O0=Z(2)[U]/(f)\mathcal{O}_0 = \mathbb{Z}_{(2)}[U]/(f), where ff is the monic lift in the theorem. It is free of rank ee over Z(2)\mathbb{Z}_{(2)}, with residue field F2e\mathbb{F}_{2^e}. Put

t=max⁡{1,⌈4⌈log⁡2s⌉/e⌉},E=et.t = \max\{1, \lceil4\lceil\log_2 s\rceil/e\rceil\}, \qquad E = et.

Then 2E≥s42^E \ge s^4 and E<e+4⌈log⁡2s⌉E < e + 4\lceil\log_2 s\rceil, except for the harmless equality case t=1t = 1. If t=1t = 1, take O=O0\mathcal{O} = \mathcal{O}_0. Otherwise choose a monic degree-tt polynomial gˉ\bar{g} irreducible over F2e\mathbb{F}_{2^e}, lift each coefficient to its binary-coordinate representative in O0\mathcal{O}_0, and write the resulting polynomial as gg. Set

O=O0[Z]/(g),Aq=O/(2q).\mathcal{O} = \mathcal{O}_0[Z]/(g), \qquad A_q = \mathcal{O}/(2^q).

The monic quotient makes O\mathcal{O} free of rank tt over O0\mathcal{O}_0. Its residue field is F2E\mathbb{F}_{2^E}, and the input ring Rp=O0/(2p)R_p = \mathcal{O}_0/(2^p) embeds as the constant-ZZ coordinates of ApA_p. In particular, this embedding is injective at every precision.

This algebra is constructible within the polynomial factor of the theorem. Enumerating monic degree-tt polynomials and testing irreducibility over the explicitly represented finite field takes 2O(et)poly⁡(e,t)2^{O(et)}\operatorname{poly}(e,t) bit operations, even using trial division by monic polynomials of degree at most t/2t/2. Since E=O(log⁡(s+L))E = O(\log(s + L)), that bound is polynomial in s+Ls + L. The construction uses the same elementary finite-field fact as Appendix D.4.1 of the source.

Units, valuation, and precision. Use the free basis UiZjU^iZ^j, 0≤i<e0 \le i < e, 0≤j<t0 \le j < t, with the evident basis when t=1t = 1. For a nonzero element, its two-adic valuation is the minimum coordinate valuation. After factoring out this power of two, its reduction in the residue field is nonzero. Products of two such reductions are nonzero, proving multiplicativity of the valuation. An element nonzero modulo two is a unit: its multiplication matrix has odd determinant, whose inverse exists in Z(2)\mathbb{Z}_{(2)}. These arguments also show that O\mathcal{O} is a domain and that its rational scalar extension is a field.

Arithmetic modulo 2q2^q, division by an explicitly known power of two with the corresponding precision loss, and unit inversion all use polynomial time and space in EE, qq and the coefficient descriptions. In particular, divisibility by 2a2^a is coordinatewise. The 2E2^E binary-coordinate residue lifts have pairwise unit differences and provide every interpolation point required in Appendix D.4.1. The recursion needs fewer than s4s^4 such points.

Entrywise lifts and the deformation. At creation precision qcq_c, each entry is represented by the integers in [0,2qc)[0,2^{q_c}) in the fixed free basis. At every later precision those same coordinates are used. This is precisely the creation-precision convention in Appendix D.4.1. It applies to input entries as well as recursively created packet tensors. Each call therefore has fixed integral lifts of its tensors, and its deformed contraction F(T)F(T) is a polynomial over the rational scalar extension of O\mathcal{O}.

The packing construction in Appendix D.4.2 depends on the network, not on its coefficients. The Cauchy kernel in Appendix D.4.3 has rational scalar coefficients, and Lemma D.4 proves their integrality after the substitution T=t0+αzT=t_0+\alpha z by cancellation of explicit integer powers of two. Consequently the same calculation gives F(t0+αz)∈O[z]F(t_0+\alpha z)\in\mathcal{O}[z] for our lifted entries. Here t0t_0 denotes a source interpolation node, distinct from the tower degree tt above. The source proof already establishes this step for arbitrary integral coefficients of its extension algebra.

Hermite recovery and mode truncation. Lemma D.5 in Appendix D.4.4 uses rational scalar Hermite multipliers. Their two-adic valuations, the jet multiplicities, and the precisions pt0p_{t_0} depend on integer interpolation nodes and the network parameters. Applying that identity in each free coordinate gives exactly the same precision loss and exact recovery modulo the parent’s precision. Interpolation from the residue-distinct values is valid because every Vandermonde difference is a unit. All intermediate precision bounds remain those of source equation (D.11).

The mode expansion in Appendix D.4.5 has coefficients divisible by the stated powers of two. Multiplication by arbitrary integral tensor entries preserves that divisibility. Thus precisely the same weighted-degree cutoff discards terms that vanish modulo 2pt02^{p_{t_0}}. The factorization into child contractions in equation (D.16) is an identity of sums and products in a commutative ring. It applies in Apt0A_{p_{t_0}}, with no change to the branch index set, child edge counts, or degree bounds.

Local descriptions and total complexity. Input entry routines are evaluated at their declared creation precision and embedded into the constant-Z\mathbb{Z} coordinates. This adds a polynomial factor in EE to their stated cost. New packet routines are the routines of Appendix D.4.6, evaluated in the fixed basis of O\mathcal{O}; their cost remains poly⁡(s+L)2O(s9/10)\operatorname{poly}(s+\mathcal{L})2^{O(s^{9/10})} with polynomial space. The descriptions and their creation precisions are shared as in the source recursion.

The node-count estimate of Appendix D.4.7 is independent of the coefficient degree. It gives 2O(s/log⁡s)2^{O(s/\sqrt{\log s})} calls, and the direct leaves and local-entry costs fit the same exponent. Arithmetic contributes a polynomial in EE, the precisions, and s+Ls+\mathcal{L}. Since E=O(log⁡(s+L))E=O(\log(s+\mathcal{L})) and all precisions are polynomial in ss, the total bound is the one stated in Theorem 4. Depth-first traversal and coordinatewise accumulators give polynomial working space.

Returning to the input ring. The root contraction is a polynomial with integer coefficients in its original entries. Its value therefore lies in the embedded Rp\mathbb{R}_p. Reading the constant-ZZ coordinates returns it; the other tower coordinates are zero modulo 2p2^p. No additional interpolation, division, or loss of precision is needed for this final extraction. This proves the extension-ring statement from the contraction argument of Theorem D.1.

References

  1. [1]Bannach, M., Demaine, E.D., Gomez, T., Hecher, M.: A Novel Reduction from #SAT to #2SAT Based on Symmetry: Simply Drop the Large Clauses (2026). https://doi.org/10.1137/1.9781611978964.19, SOSA, pp. 254–265
  2. [2]Claude (Anthropic): A 2^{o(n)} Time Algorithm for 3-SAT (2026), https://github.com/anthropics/formal-math/blob/main/eth/paper.pdf, 26 October 2026
  3. [3]Jahanjou, H., Miles, E., Viola, E.: Local Reductions (2013), https://arxiv.org/abs/1311.3171, ECCC TR13-099; arXiv:1311.3171
  4. [4]Laakkonen, T., Meichanetzidis, K., van de Wetering, J.: A Graphical #SAT Algorithm for Formulae with Small Clause Density (2024). https://doi.org/10.4204/EPTCS.406.7, https://arxiv.org/abs/2212.08048, EPTCS 406, 137–161
  5. [5]OpenAI: The Exponential Time Hypothesis is False. OpenAI Math Release preprint (2026), https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 25 October 2026
  6. [6]Tamaki, S.: A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates (2016), https://eccc.weizmann.ac.il/report/2016/100/, ECCC TR16-100
  7. [7]Williams, R.: Improving Exhaustive Search Implies Superpolynomial Lower Bounds (2013). https://doi.org/10.1137/10080703X, https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf, SIAM Journal on Computing 42(3), 1218–1244

Paper details

vlnc:W_dvvjy6kx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents