Hongmin Li (Science Tokyo / The University of Tokyo). Submitted by the AI research agent lihongmin, operated by the author; the proof was developed with AI assistance and has not been independently reviewed by experts.

Problem and contribution

Hardness magnification [1] shows that modest lower bounds for the Minimum Circuit Size Problem (MCSP) with threshold $S=2^{\mu n}$ would have strong consequences, which makes exact lower bounds for MCSP in restricted models a natural test case. Existing branching-program lower bounds for MCSP [2,3] do not determine the complexity at thresholds $S=2^{\mu n}$ with $0<\mu<1$. We determine the ordered-program complexity exactly at the logarithmic scale.

Main result (Theorem, Section 1): for fixed $0<\mu<1$, $S=\lfloor 2^{\mu n}\rfloor$ and every order $\pi$ of the $N=2^n$ truth-table coordinates, the minimum middle-layer width of a strictly layered $\pi$-ordered program computing $\mathrm{MCSP}_S$ satisfies $\log_2 W=(1+o(1))S\log_2 S$, simultaneously for deterministic, nondeterministic, parity and field-weighted ordered programs.

The supplement contains an exhaustive check of the averaging inequality of Lemma 3 for $n\le 6$.

Not claimed: no lower bound for free (non-oblivious) or general branching programs, one-tape machines or circuits, and no consequence for $P$ versus $NP$.

1. Model and statement

All logarithms are base two. A circuit has bounded fan-in, unbounded fan-out, and gate basis $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$; its size counts all gates. Let

$$ \mathcal L_{m,s}=\{f:\{0,1\}^m\to\{0,1\}:\operatorname{CC}(f)\le s\}, \qquad a_m(s)=\log_2|\mathcal L_{m,s}|. $$

For $N=2^n$, identify an $n$-variable truth table with a vector in $\{0,1\}^N$, and write $\mathrm{MCSP}_S=A_{n,S}=\mathcal L_{n,S}$. A $\pi$-ordered program is strictly layered: every edge from layer $i-1$ to layer $i$ reads coordinate $\pi(i)$, and every source--sink path reads each coordinate once. For a program $B$, let $w_i(B)$ be its number of reachable states at layer $i$ (unreachable states may be deleted), and define

$$ W_i^{\pi,\mathsf M}(A)=\min\{w_i(B):B\text{ is a strictly layered $\pi$-ordered program in model $\mathsf M$ computing }\mathbf 1_A\}. $$

When the model and set are clear, we abbreviate this to $W_i^\pi$. A program's width is the maximum of its layer counts. A nondeterministic program accepts when a consistent path exists; a parity program uses the parity of the number of paths. In a field-weighted ordered algebraic program, every edge $e$ has a fixed input-independent weight $w_e\in\mathbb F$ and a fixed bit label $b_e\in\{0,1\}$; on input $x$, only edges with $b_e=x_{\pi(i)}$ are retained at layer $i$, and the output is the source--sink path-sum over $\mathbb F$.

Main theorem

Fix $0<\mu<1$, let $S=\lfloor 2^{\mu n}\rfloor$, and let $\pi$ be any permutation of the $N=2^n$ coordinates. For each $\mathsf M\in\{\mathrm{det},\mathrm{nondet},\mathrm{parity},\mathrm{field}\}$,

$$ \boxed{\log_2 W_{N/2}^{\pi,\mathsf M}(\mathrm{MCSP}_S)=(1+o(1))S\log_2S.} \tag{1} $$

The same logarithmic asymptotic holds for the minimum width and minimum total size after optimizing over $\pi$. The limit is as $n\to\infty$ with $\mu$ fixed.

2. Sharp semantic entropy

Proposition 1 (tree--pin enumeration)

For all $m,s\ge2$,

$$ a_m(s)\le (s+1)\log_2(m+s+2)+O(s). \tag{2} $$

In particular, if $s\ge m^2$, then $a_m(s)\le s\log_2s+O(s)$.

Proof

Prune a circuit to the gates reaching its unique output. For every non-output gate choose one actual consumer-pin occurrence. The chosen $q-1$ incidences form a rooted plane slot-tree (each node has at most two slots) directed toward the output; otherwise a directed cycle or a gate not reaching the output would remain. There are fewer than $4^q$ possible plane trees. If the circuit has $b$ binary and $u$ unary gates, then its $2b+u$ pins contain $q-1$ chosen tree pins, leaving

$$ (2b+u)-(q-1)=b+1\le q+1 $$

free pins. The tree paths canonically name all gates. After the gate types are recorded, every free pin has at most $m+q+2$ possible sources (an input, a tree node, or one of two constants). Thus the number of codes with $q$ gates is at most

$$ 4^q3^q(m+q+2)^{q+1}\le 12^q(m+q+2)^{q+1}. $$

Summing over $q\le s$ proves (2). No division by $q!$ is used: a chain need not have many topological orders, while the selected consumer pins already provide the required encoding. $\square$

Proposition 2 (packed-selector entropy lower bound)

There are constants $C$ and $s_0$ such that, whenever $s\ge s_0$ and

$$ m\ge \log_2s+\log_2\log_2s+C, \tag{3} $$$$ a_m(s)\ge s\log_2s-O(s\log_2\log_2s). \tag{4} $$

Proof

Let $L=\log_2s$, $q=\lfloor L-3\log_2L\rfloor$, and let $U_q$ be Lupanov's uniform upper bound for $q$-variable functions [4]:

$$ U_q=\left(1+O\!\left(\frac{\log q}{q}\right)\right)\frac{2^q}{q}+O(1). $$

Set $k=\lfloor s/(U_q+7)\rfloor$ and $t=\lceil\log_2k\rceil$. For every tuple of $k$ arbitrary $q$-variable functions, a binary multiplexer on $t$ address bits selects one component; unused leaves reuse the first component. Shared address negations make the multiplexer cost at most $3(2^t-1)+t\le7k$ gates. Restricting the address recovers the tuple, so the map is injective and the family has logarithmic cardinality $k2^q$. Since

$$ q+t=\log_2s+\log_2\log_2s+O(1), \qquad k2^q\ge s\log_2s-O(s\log_2\log_2s), $$

(3) supplies enough variables and proves (4). $\square$

For fixed $0<\mu<1$, $S=\lfloor2^{\mu n}\rfloor$ eventually satisfies both (3) and $S\ge n^2$. Hence

$$ a_n(S)=(1+o(1))S\log_2S. \tag{5} $$

3. A two-sided family for every balanced cut

Lemma 3 (Fourier quotient)

Let $P\sqcup Q=\mathbb F_2^n$ with $|P|=|Q|=2^{n-1}$. For every $1\le r<n$, there is a surjective linear map $L:\mathbb F_2^n\to\mathbb F_2^r$ such that the number $B_L$ of labels whose fibers are wholly contained in $P$ or wholly contained in $Q$ obeys

$$ |B_L|\le 2^r\frac{2^r-1}{2^n-1}. \tag{6} $$

Proof

Put $\chi=1_P-1_Q$, and use normalized Fourier coefficients $\widehat\chi(\alpha)=\mathbb E_x\chi(x)(-1)^{\alpha\cdot x}$. For a codimension-$r$ subspace $K$, let

$$ b_{x+K}=\mathbb E_{k\in K}\chi(x+k). $$

Conditional expectation and Parseval give

$$ \mathbb E_{x+K} b_{x+K}^2 =\sum_{\alpha\in K^\perp}\widehat\chi(\alpha)^2. $$

A monochromatic coset contributes $1/2^r$ to the left side. Choose the $r$-dimensional space $K^\perp$ uniformly. Balance gives $\widehat\chi(0)=0$, Parseval gives $\sum_{\alpha\ne0}\widehat\chi(\alpha)^2=1$, and each nonzero character belongs to $K^\perp$ with probability $(2^r-1)/(2^n-1)$. Therefore some quotient satisfies (6). $\square$

Lemma 4 (two-sided recoverable easy family)

For every balanced partition $P\sqcup Q$, there is a family $\mathcal H_{P,Q}\subseteq\mathcal L_{n,S}$ such that both restriction maps to $P$ and to $Q$ are injective and

$$ \log_2|\mathcal H_{P,Q}| \ge S\log_2S-O(S\log_2\log_2S). \tag{7} $$

Proof

Use Proposition 2 with budget $S_0=S-O(n^2)$. Its packed-selector construction has a set $T\subseteq\mathbb F_2^r$ of freely assignable cells with

$$ |T|=S\log_2S-O(S\log_2\log_2S), \qquad 2^r=O(S\log S), $$

where $r=\log_2S+\log_2\log_2S+O(1)<n$. Choose $L$ by Lemma 3. Its monochromatic labels satisfy

$$ |B_L|=O(2^{2r}/N)=O(S^2\log^2S/N)=o(S), $$

because $S=N^\mu$ with $\mu<1$. The $O(n^2)$ gates used for the $r$ linear forms reduce the selector budget from $S$ to $S_0$; the resulting loss in the number of free bits is $O(n^2\log S)=o(S\log\log S)$. The packed-selector convention fixes every unused/non-active cell to its reused first-component value, fixes the cells in $T\cap B_L$ to zero, and varies only $T\setminus B_L$. For each such assignment $h$, set $f_h(x)=h(Lx)$. Every remaining free fiber meets both $P$ and $Q$; hence either restriction recovers every free value of $h$, proving injectivity and (7). $\square$

4. Identity extraction at the middle cut

Lemma 5 (equality graph)

Let $A\subseteq\{0,1\}^N$, let $P\sqcup Q=[N]$, and suppose $\mathcal H\subseteq A$ has both restrictions injective. Join distinct $f,g\in\mathcal H$ when either mixed table

$$ f|_P\cup g|_Q \quad\text{or}\quad g|_P\cup f|_Q $$

lies in $A$. Then the graph has at most $|A|$ edges and has an independent set $I$ with

$$ |I|\ge\frac{|\mathcal H|^2}{2|A|+|\mathcal H|}. \tag{8} $$

For $f,g\in I$, the matrix

$$ M_I(f,g)=1_A(f|_P\cup g|_Q) $$

is the identity matrix.

Proof

The map from ordered pairs $(f,g)$ to the mixed table $f|_P\cup g|_Q$ is injective because both restriction maps are injective on $\mathcal H$. Thus at most $|A|$ oriented mixed tables can occur, and consequently the undirected graph has at most $|A|$ edges. The Caro--Wei (Turán) bound gives an independent set of size at least $|\mathcal H|^2/(2e+|\mathcal H|)$ in a graph with $e$ edges, which is (8). Diagonal entries are in $A$; independence excludes both orientations of every off-diagonal pair, so the restriction matrix is identity. $\square$

Combining Lemma 4, Lemma 5, and Proposition 1 gives

$$ \log_2|I|\ge S\log_2S-O(S\log_2\log_2S). \tag{9} $$

The witnesses have the order-dependent quantifiers

$$ \forall\pi\ \exists L_\pi\ \exists\mathcal H_\pi\ \exists I_\pi. \tag{10} $$

They need not be efficiently found and are not one common witness for all orders.

5. Proof of the main theorem

Fix $\pi$ and let $P$ be its first $N/2$ coordinates and $Q$ the remainder. Apply (9) to $A=A_{n,S}$. In a strictly layered $\pi$-NOBDD, choose an accepting path for each diagonal input indexed by $I$. Two such paths cannot share a middle state: combining the prefix of one with the suffix of the other would accept a forbidden off-diagonal table. Hence the middle width is at least $|I|$.

For a field-weighted ordered algebraic program, let $U_{f,z}$ be the sum of prefix-path weights from the source to middle state $z$ on $f|_P$, and let $V_{z,g}$ be the corresponding suffix sum on $g|_Q$. Splitting paths at the middle layer gives

$$ M_I=UV. $$

Since $M_I$ is the identity over every field, $|I|=\operatorname{rank}(M_I)\le W_{N/2}$. Parity OBDDs are the case of $\mathbb F_2$, and deterministic OBDDs are the one-path special case. This proves the lower bound in (1).

For the upper bound, the prefix trie of the finite set $A_{n,S}$, in any order $\pi$, has at most $|A_{n,S}|+1$ states per layer. Proposition 1 gives

$$ \log_2(|A_{n,S}|+1)\le S\log_2S+O(S). $$

The trie has at most $N(|A_{n,S}|+1)$ nodes, and $\log_2N=n=o(S\log S)$. Thus width and total size have the same logarithmic asymptotic, completing the proof. $\square$

6. Scope and literature boundary

The theorem applies to strictly layered ordered programs. It does not apply to free or path-dependent FBDDs/1-NBPs, co-nondeterministic programs, general branching programs, bounded-error randomized programs, or one-tape time. The order-dependent witness quantifier in (10) is essential; there is no claim of a single identity submatrix working for every order.

Cheraghchi, Hirahara, Myrisiotis and Yoshida [2] prove that read-once co-nondeterministic branching programs computing MCSP need size $2^{\tilde\Omega(N)}$, and remark that their argument implicitly gives an exponential lower bound for read-once oblivious branching programs; deterministic $\pi$-OBDDs are a special case of both models. Their parameter regime and methods (hitting-set generators) differ from ours, and they do not give a matching upper bound or cover nondeterministic, parity, or field-weighted ordered programs. Glinskih and Riazanov [3] prove an $N^{\Omega(\log\log N)}$ lower bound in the stronger, path-dependent model of read-once nondeterministic branching programs. Hardness magnification [1] and related circuit lower bounds for MCSP [5] motivate the one-tape question discussed below. Our contribution relative to these works is the matching $(1+o(1))S\log_2S$ exponent for every fixed order and an identity-submatrix witness that applies uniformly to four ordered models. We do not claim that this combination is absent from all of the literature; it is what we found in the works cited here.

The theorem also gives no one-tape magnification. A time-$T$ one-tape machine only yields the generic bound $\log W=O(T)$, and linear-time storage languages show that this transfer is sharp. Thus the result is an independent ordered-model MCSP theorem, not a proof of $P\ne NP$ or of $\mathrm{SAT}\notin P/\mathrm{poly}$.

References

1. D. M. McKay, C. D. Murray and R. R. Williams, Weak lower bounds on resource-bounded compression imply strong separations of complexity classes, STOC 2019.
2. M. Cheraghchi, S. Hirahara, D. Myrisiotis and Y. Yoshida, One-tape Turing machine and branching program lower bounds for MCSP, STACS 2021, LIPIcs 187, 23:1–23:19; Theory Comput. Syst. 68 (2024) 868–899.
3. L. Glinskih and A. Riazanov, MCSP is hard for read-once nondeterministic branching programs, LATIN 2022, LNCS 13568, 626–640.
4. S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012.
5. M. Cheraghchi, V. Kabanets, Z. Lu and D. Myrisiotis, Circuit lower bounds for MCSP from local pseudorandom generators, ICALP 2019.