Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 112: beyond the square-root exponent for depth-three Boolean circuits

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This article records the claim in a pinned publisher catalogue; it does not independently verify the circuit lower bound.

The question in plain language

A Boolean circuit computes a yes-or-no answer from binary inputs. A depth-three OR–AND–OR circuit first combines input literals with OR gates, groups those results with AND gates, and finally combines the groups with one OR gate. Allowing gates to have arbitrarily many inputs makes this a powerful but tightly structured computational model.

The central question is whether we can explicitly describe a Boolean function that cannot be implemented by a small circuit of this shape. Family 112 claims a construction exceeding the long-studied square-root exponent in lower bounds for this particular model.

A small example

An OR–AND–OR circuit can check several alternative conditions: each condition is an AND of clauses, and each clause is an OR of literals. It can thus represent a disjunction of conjunctions of disjunctions.

The size in the claimed theorem counts total gates, not only gates on one layer or the number of input wires. An unbounded-fan-in gate can have many incoming wires, so gate count and wire count are different complexity measures.

For an input length \(n\), a bound like \(2^{c\sqrt n}\) is exponential in the square root rather than in \(n\). The stronger \(2^{\omega(\sqrt n)}\) means that the exponent divided by \(\sqrt n\) tends to infinity; it is not interchangeable with merely \(2^{\Omega(\sqrt n)}\).

What is known

The protected Family 112 catalogue identifies a single manuscript, Beyond the Square-Root Exponent for Depth-Three Boolean Circuits.

The pinned publisher overview claims that one language decidable in deterministic polynomial time has membership functions on \(n\) input bits that require

\[ 2^{\omega(\sqrt n)} \]

total gates in unbounded-fan-in OR–AND–OR circuits, for every sufficiently large input length \(n\).

The assertion of one fixed polynomial-time language matters: it is not just a nonuniform counting argument showing that some hard function exists at each input length. Likewise, “every sufficiently large length” is stronger than a lower bound holding only at infinitely many lengths.

The claim is specific to depth-three OR–AND–OR circuits. It does not by itself imply a comparable bound for arbitrary Boolean circuits, larger circuit depth, or general polynomial-time computation, and it is not a proof that \(\mathsf P\ne\mathsf{NP}\).

GCL verification state

The source is pinned to openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The GCL catalogue identifies the manuscript path and the overview attributes the language construction, total gate count, circuit class and all-large-length quantifier to the publisher.

This documentary pass has not verified the explicit membership algorithm, its uniform polynomial running time, the lower-bound proof, input literal conventions, fan-in convention, size accounting, or the uniformity in \(n\). No Family 112-specific accepted proof criticism, Lean trust-chain audit, Comparator determination, or MATHCERT certificate is asserted.

What remains

Read the pinned PDF and extract the exact circuit model, including constants, negation placement, repeated literals, possible constant gates and whether wires or only gates are counted. Reconstruct the language's deterministic decision algorithm and prove its polynomial-time bound without unacknowledged advice or nonuniform information.

Audit the lower-bound argument across all sufficiently large \(n\) and demonstrate precisely why its exponent is \(\omega(\sqrt n)\) rather than a fixed multiple of \(\sqrt n\). Verify how small or exceptional lengths are handled and whether reductions preserve the OR–AND–OR depth convention.

Complete documentary validation, mathematical Markdown/MkDocs rendering, source-critical review and protected merge/readback. Editorial acceptance would not certify this circuit lower bound.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. The complexity lower bound is a publisher-reported claim pending independent verification.


Indexed primary manuscript paths: