# A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input size). I would like to prove there exists a decidable language that doesn't belong to the set defined above. I tried using a fixed input size and using an upper bound for the number of possible languages that can be implemented by such circuit, and to show it is a polynomial upper bound (while there are 2^2^n languages). Problem is, I'm pretty sure this proof doesn't hold, because this circuit ensemble consists of C_n which can be in size n2^n and all other circuits are constant on 0, and since n is fixed it can be perceived as an O(1) upper bound for all circuits.

If anyone could help I'd very much appreciate. Thanks

• It might be killing a fly with a hammer, but I think this follows from time hierarchy theorem and the fact that a linear size circuit can be evaluated in time $O(n^2)$. That is, by time hierarchy, there exist languages which require time $\Omega(n^3)$, so take one of those languages. Certainly it cannot have a linear size circuit. Commented Jan 3 at 2:57
• @nosyarg A function of linear circuit complexity is not necessarily computable in time $O(n^2)$; it may not be computable at all. You are only given the input to the function, not a description of the circuit that computes the function, and there is no reason the circuit should be efficiently computable. Commented May 2 at 10:13

You can show more: there is a function in $$\mathsf{EESPACE}$$ (doubly exponential space) which has maximal circuit complexity. Given an input $$x$$ of length $$n$$, enumerate all Boolean circuits with $$n$$ inputs in increasing order of size, until you encounter all Boolean functions. Choose a Boolean function $$f$$ of maximal circuit complexity, and output $$f(x)$$.

• This is an overkill. First, truth-tables of functions $f\colon\{0,1\}^n\to\{0,1\}$ and circuits of size up to $2^n$ can be represented by $2^{O(n)}$ bits, hence the lexicographically first function of maximal circuit complexity can be computed in singly exponential space. In fact, since the defining condition only requires alternation of quantifiers of fixed depth, it can be computed in the exponential hierarchy: a simple direct argument gives $\mathsf{\Sigma^{EXP}_3\cap\Pi^{EXP}_3}$, a slightly more clever binary search gives $\mathsf{\Delta^{EXP}_3=EXP^{\Sigma^P_2}}$. Commented May 2 at 9:24
• And, of course, languages of superlinear circuit complexity can be found in a much lower class (within polynomial hierarchy) than languages with maximal circuit complexity. Commented May 2 at 9:25
• (For completeness, I should add that a language of not-quite-maximal circuit complexity $\Omega(2^n/n)$ can be found in $\mathsf{S^{EXP}_2}$ by a recent result of Li eccc.weizmann.ac.il/report/2023/156 .) Commented May 2 at 10:18

$$\let\S\mathsf$$Such a language can be found within a low level of the polynomial-time hierarchy:

1. For each $$n$$, there exist Boolean functions $$f\colon\{0,1\}^n\to\{0,1\}$$ of superlinear circuit complexity; in fact, of complexity $$\Omega(2^n/n)$$.

This follows by a simple counting argument: there are $$2^{2^n}$$ Boolean functions, but only $$(s+n)^{O(s)}=2^{O(s\log s)}$$ circuits of size $$s\ge n$$, thus some functions are not computable by circuits of size $$s$$ where $$s=\Omega(2^n/n)$$.

2. Let $$f_n\colon\{0,1\}^n\to\{0,1\}$$ denote the function of circuit complexity $$\ge n^2$$ with lexicographically first truth table $$\mathrm{tt}_{f_n}\in\{0,1\}^{2^n}$$ (which exists by 1). Then the language $$L=\{w:f_{|w|}(w)=1\}$$ is decidable (and clearly needs circuit size $$\ge n^2$$).

To decide $$w\in L$$, just enumerate all functions $$f\colon\{0,1\}^n\to\{0,1\}$$, $$n=|w|$$, in lexicographic order until you find one with circuit size $$\ge n^2$$; the latter condition is again decidable by enumerating all circuits of a given size.

3. The language $$L$$ from 2 is in the polynomial-time hierarchy.

The function $$f_n$$ from 2 is easily seen to have circuit size $$O(n^2)$$. Thus, instead of truth tables of functions $$f$$, you can enumerate circuits $$C$$ of quadratic size that represent them. You can test whether two circuits represent the same function in $$\S{coNP}$$, thus given $$C$$, you can test whether $$C$$ is equivalent to a circuit of size $$ in $$\S{\Sigma^P_2}$$. Likewise, you can test whether the function $$f_D$$ computed by a circuit $$D$$ is lexicographically strictly before $$f_C$$ in $$\S{\Sigma^P_2}$$ (“there is $$x\in\{0,1\}^n$$ such that $$D(x)=0$$, $$C(x)=1$$, and for all $$y<_{\mathrm{Lex}}x$$, $$C(y)=D(y)$$”). Thus, “there is a function $$f$$ lexicographically smaller than $$f_C$$ of circuit complexity $$\ge n^2$$” is $$\S{\Sigma^P_3}$$, and “$$f_C$$ is the lexicographically first function of circuit size $$\ge n^2$$” is $$\S{\Pi^P_3}$$. Thus, you can guess such a circuit $$C$$, verify it, and evaluate it on the given input $$w$$ in $$\S{\Sigma^P_4}$$ (and $$\S{\Pi^P_4}$$).

4. There is a language $$L\in\S{(NP\cup O^P_2)\subseteq S^P_2\subseteq ZPP^{NP}\subseteq(\Sigma^P_2\cap\Pi^P_2)}$$ that requires superlinear circuit size. (See $$\S{S^P_2}$$, $$\S{O^P_2}$$ if you are unfamiliar with these classes.)

We distinguish two cases. First, if some language $$L\in\S{NP}$$ has superlinear circuit complexity, we are done. Otherwise, if all languages in $$\S{NP}$$ have linear-size circuits, then $$\S{NP\subseteq P/poly}$$, thus $$\S{PH=O^P_2}$$, thus the language from 2 and 3 is computable in $$\S{O^P_2}$$.

5. Addendum: There is a language $$L\in\S{O^P_2}$$ that requires superlinear circuit size (but it takes some effort to prove this).

This follows from recent work of Li, who proves that there is a single-valued $$\S{FS^P_2}$$ algorithm for the range-avoidance problem (which has been for a long time called the dual or surjective weak pigeonhole principle in literature on bounded arithmetic): given a circuit $$C\colon\{0,1\}^m\to\{0,1\}^{m+1}$$, find $$y\in\{0,1\}^{m+1}$$ which is not in the range of $$C$$. The main application in the paper is that there is a language in $$\S{S^E_2}$$ (actually, $$\S{O^E_2}$$) that requires circuit complexity $$\Omega(2^n/n)$$, but the same argument scalled down gives a language in $$\S{O^P_2}$$ that requires circuit complexity $$\Omega(n^2)$$. This is spelled out in Gajulapalli, Li & Volkovich.

Define $$L$$ as follows: given an input $$w$$ of size $$n$$, let $$C$$ be a circuit implementing the poly-time function that takes as input a description of a circuit $$D\colon\{0,1\}^{3\log n}\to\{0,1\}$$ of size at most $$n^2$$, and outputs its truth table. Since $$D$$ takes $$O(n^2\log n)$$ bits to describe, but the truth table has $$n^3$$ bits, we can apply the range-avoidance algorithm to find the truth table of a function $$f\colon\{0,1\}^{3\log n}\to\{0,1\}$$ that is outside the range of $$C$$, i.e., that requires circuit size $$\ge n^2$$. Then $$w\overset?\in L$$ is determined by the value of $$f$$ applied to the first $$3\log n$$ bits of $$w$$. The resulting language still requires circuit size $$\ge n^2$$, and it is computed by an $$\S{S^P_2}$$ algorithm. Moreover, this algorithm is oblivious (i.e., an $$\S{O^P_2}$$ algorithm) because we only use $$n$$, rather than $$w$$, to find $$f$$.

The whole argument works with obvious adaptations not just for circuits of size $$O(n)$$, but more generally, for circuits of size $$O(n^c)$$ for a fixed constant $$c$$.