P versus NC^1

P versus NC^1

Definitions and mathematical statement

A De Morgan formula is a Boolean circuit whose computation graph is a tree, using AND, OR, and NOT. Its size counts its gates or symbols, up to the usual polynomially equivalent conventions. The target is a uniformly polynomial-time computable family $f_n:\{0,1\}^n\to\{0,1\}$ with \[ \operatorname{FormulaSize}(f_n)\text{ not bounded by any polynomial in }n. \] The formulas themselves are nonuniform. This is the assertion $\mathsf P\nsubseteq\mathsf{NC}^1$ for nonuniform $\mathsf{NC}^1$; an absence of a uniform shallow-circuit construction would be weaker.

Formulation and concept references: [S1].

Short English statement

Is there an efficiently computable Boolean function family that no polynomial-size formula family can represent?

Research attempt

Current frontier.

The source studies the Karchmer--Raz--Wigderson composition route to superpolynomial formula lower bounds, retaining nonuniform formulas and uniform polynomial-time computation [S1], Introduction. Chukhin--Kulikov--Mihajlin's 2024--2025 work treats a strong communication composition involving XOR and a random function; its bounds do not directly become formula-depth bounds for arbitrary iterated compositions [E1]. We will not assume such a transfer. The attempt makes the hard inner functions uniformly computable at the final input length and isolates an iterated-depth assertion sufficient for the exact target.

Attack route.

Counting produces hard functions but usually loses uniformity. Direct subfunction counting is limited by the amount of information available from a single partition. Composition could amplify hardness if losses do not accumulate too quickly. We combine exhaustive selection at very small arity with a large composition tree, explicitly account for the selection time, and then test whether an elementary subfunction method could prove the missing amplification.

Attempt: canonical hard seeds without advice.

Let $L(f)$ be the minimum leaf size of a De Morgan formula, with negations pushed to inputs, and let $D(f)$ be minimum fan-in-two AND/OR/NOT circuit depth. Unrolling gives $L(f)\le2^{D(f)}$; formula balancing gives an absolute $C_0$ such that \begin{equation}\label{wsref-0-72-36-39-3a-62-61-6c-61-6e-63-65} D(f)\le C_0\log_2(L(f)+2). \end{equation} The balancing statement, including its polynomial size overhead, is recalled in [S1], page 2. Gates and leaf conventions change only fixed polynomial factors.

For integers $b\ge8$, set \[ u_b=\lceil\log_2(32b)\rceil,\qquad s_b=\left\lfloor\frac{2^b}{4u_b}\right\rfloor. \] Binary tree shapes, internal AND/OR labels, and literal or constant leaves give at most $2(32b)^{s_b}$ formula descriptions with at most $s_b$ leaves. This is bounded by $2^{1+2^b/4}$. There are at least \[ \binom{2^b}{2^{b-1}}\ge\frac{2^{2^b}}{2^b+1} \] balanced truth tables, by taking the largest binomial coefficient. This exceeds the description bound. Define $g_b$ to be the lexicographically first balanced table not computed by those formulas. Then \begin{equation}\label{wsref-0-72-36-39-3a-73-65-65-64} L(g_b)>s_b,\qquad D(g_b)\ge\log_2(s_b+1)=b-O(\log b). \end{equation} This definition is algorithmic: enumerate candidate balanced tables and all the short formulas, evaluating each on its $2^b$ inputs. The total time is $2^{O(2^b)}$, with an absolute constant in the exponent, not an oracle for formula complexity. The enumeration deliberately allows constants, making its hardness conclusion only stronger than one obtained by forbidding them.

Place the expensive search at logarithmic-logarithmic arity.

For a sufficiently large final input length $N$, choose \[ b=\lfloor\log_2\log_2N\rfloor,\qquad h=\lfloor\log_b N\rfloor, \qquad m=b^h\le N<bm. \] Define $F_N$ on its first $m$ inputs by a full $b$-ary tree of height $h$, applying $g_b$ at every internal node. Ignore the remaining inputs. Equivalently, it is $g_b^{\circ h}$ with dummy variables appended. For the finitely many lengths with $b<8$, choose any explicitly specified function.

The seed search costs $2^{O(2^b)}\le N^{O(1)}$. The tree has fewer than $2N$ nodes, and the seed table has at most $\log_2N$ entries. Even scanning the table at every evaluation gives polynomial total time. Integer counters compute $b,h,m$; no real-arithmetic oracle is used. Thus $(F_N)$ is a uniformly polynomial-time computable family, rather than a nonuniform choice of random hard seeds.

\begin{notebookproposition} Suppose an absolute $c>0$ satisfies \begin{equation}\label{wsref-0-72-36-39-3a-6d-69-73-73-69-6e-67}
 D(g_b^{\circ h})\ge c h D(g_b)
\end{equation} for the pairs $(b,h)$ above at all sufficiently large $N$. Then the family $(F_N)$ proves the target $\mathsf P\nsubseteq\mathsf{NC}^1$. \end{notebookproposition}

This is a restricted iterated self-composition hypothesis for the selected seeds, not an assertion of the general KRW conjecture. It is unproved. A fixed loss in a two-function composition theorem cannot simply be iterated and then replaced by the same fixed loss for a height-$h$ tree: it may compound with $h$. Nor can the strong communication-composition statement in [E1] be substituted for (r69:missing). The latter is a statement about actual Boolean circuit depth.

Try a lower-bound method on the constructed family.

Partition the $N$ inputs into nonempty disjoint blocks of sizes $b_1,\ldots,b_q$. Let $r_i$ be the number of distinct functions of block $i$ obtained by fixing every outside input. Universally, \begin{equation}\label{wsref-0-72-36-39-3a-73-75-62-66-75-6e-63-74-69-6f-6e-73} \log_2r_i\le\min\{2^{b_i},N-b_i\}. \end{equation} For a formula with $\ell_i$ occurrences of variables from block $i$, mark those leaves and retain their connecting tree. Each path between retained branch points, after fixing outside variables, acts as one of the four unary Boolean maps. There are at most $2\ell_i+1$ such segments if a root segment is included. The original marked leaf labels are fixed. Hence $r_i\le4^{2\ell_i+1}$, including the constant-function case $\ell_i=0$. Summing gives the familiar subfunction budget \[ L(F_N)\ge\tfrac14\left(\sum_i\log_2r_i-2q\right). \] This is a version of the Nečiporuk mechanism; abstract limitations of such methods are investigated in [E2]. The following particular ceiling is elementary and does not rely on importing a theorem for a different circuit model.

If $b_i<\frac12\log_2N$, its contribution to (r69:subfunctions) is at most $\sqrt N$, and there are at most $N$ blocks. Larger blocks number at most $2N/\log_2N$ and contribute at most $N$ each. Therefore \[ \sum_i\log_2r_i\le N^{3/2}+\frac{2N^2}{\log_2N} =O(N^2/\log N). \] No choice of this single partition budget can supply (r69:lower). This is not a universal barrier to formula lower bounds; it only rules out the particular measure just derived. The hoped-for proof must use more than separate counts of possible subfunctions on disjoint blocks.

Stress test.

The hard-seed search is performed by one uniform algorithm within polynomial time at length $N$, although it would be prohibitive at seed input length $b$ alone. Formula hardness is not assumed to imply depth hardness in both directions without balancing; both implications needed above were explicitly stated. Dummy variables do not create a lower bound, but restriction preserves the existing one. Balanced seeds are nonconstant and the description count is compared with balanced, not all, functions.

The script exhausts all three-variable Boolean functions by minimum formula leaf size and checks the integer counting inequalities used for larger $b$. All 256 three-variable functions are reached; the maximum minimum leaf size is 10, including among balanced functions. Those tests validate the finite enumeration mechanism, not the iterated-depth hypothesis. No computer calculation is asserted to prove (r69:missing) at unbounded arity and height. The conclusion would be the precise uniform-$\mathsf P$ versus nonuniform-formula separation, not an asserted $\mathsf P\ne\mathsf{NP}$ consequence.

Outcome.

Outcome: Conditional reduction.

A fully uniform candidate family is constructed, with explicit seed-search cost. A precise iterated-depth estimate for that family would give the superpolynomial bound (r69:lower). The elementary subfunction attack has a proved polynomial ceiling, so it cannot establish that estimate. The missing composition inequality remains substantial and is not inferred from existing partial KRW results; neither the lower bound for this family nor the target separation is claimed unconditionally.

Sources

• S1 Gavinsky, Meir, Weinstein, and Wigderson, ECCC TR13-190, revision 11, 2017. https://eccc.weizmann.ac.il/report/2013/190/revision/11/download. Catalogue formulation source.
• S2 Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. https://arxiv.org/abs/2410.10189. Catalogue research/status reference; not a proof endorsement.
• S3 Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. https://epubs.siam.org/doi/10.1137/15M1018319. Catalogue research/status reference; not a proof endorsement.

• E1 Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin, Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function, arXiv:2410.10189v3 (29 January 2025); STACS 2025. https://arxiv.org/abs/2410.10189v3. Strong communication composition does not directly prove the notebook's iterated Boolean-depth hypothesis. Consulted 27 September 2026.
• E2 Paul Beame, Nathan Grosshans, Pierre McKenzie, and Luc Segoufin, Nondeterminism and an abstract formulation of Nečiporuk's lower bound method, arXiv:1608.01932 $2016$, DOI 10.1145/3013516. https://arxiv.org/abs/1608.01932. Framework for method-specific limitations; the single-partition ceiling used here is proved directly. Consulted 27 September 2026.