NP-Completeness of the Minimum Circuit Size Problem (MCSP)

NP-Completeness of the Minimum Circuit Size Problem (MCSP)

Definitions and mathematical statement

The input to MCSP is the full $2^n$-bit truth table of $f:\{0,1\}^n\to\{0,1\}$ and an integer size bound $s$. Using a fixed standard complete Boolean basis, define \[ \mathsf{MCSP}=\{(\operatorname{tt}(f),s):\exists C, |C|\le s,\ C(x)=f(x)\ \forall x\in\{0,1\}^n\}. \] The question is NP-hardness under deterministic polynomial-time many-one reductions, with running time measured in truth-table input length. A succinct or implicitly specified truth table defines a different problem. Randomized or non-many-one hardness reductions do not establish the selected reduction type.

Formulation and concept references: [S1].

Short English statement

Is finding whether a complete Boolean truth table has a small circuit NP-hard under ordinary deterministic many-one reductions?

Research attempt

Current frontier.

The June 2026 formulation source explicitly leaves open deterministic, polynomial-time, many-one hardness for the explicit truth-table problem. Its new hardness result concerns an implicitly sampled function, uses randomness, and assumes subexponential cryptography and proof-complexity hypotheses. None of those qualifications can be discarded. [S1] Hirahara--Ilango obtain conditional hardness with quasipolynomial-time nonadaptive reductions, not the reduction requested here. [E1]

Attack route.

Try to transfer hardness from minimization of partial truth tables to total ones. A partial table $p:\{0,1\}^n\to\{0,1,*\}$ specifies only some values; write $C^*(p)=\min_{f\supset p}C(f)$. Three possible routes are a canonical completion, a selector encoding all completions, and a robust gap gadget. The first two can be tested without assuming a conjecture. The third needs a totalization theorem with a controlled gap for unrestricted circuits, not just a gadget working on the intended representations. The following elementary deductions are developed for this notebook; no historical novelty is asserted.

Attempt: canonical completion loses the existential witness.

Use first the basis of all binary gates, free input wires and free constants; a fixed complete basis changes the upper bounds below by constant factors. For any total $h$, put \[ p_h(x)=\begin{cases}1&h(x)=1,\\ *&h(x)=0.\end{cases} \] Then $C^*(p_h)=0$, using constant one, whereas zero-filling produces exactly $h$. Thus zero-filling can turn a trivial partial instance into an arbitrarily hard total function. One-filling has the symmetric defect using specified zeros. Charging one gate for a constant only changes a fixed additive cost.

For completeness, circuits with $s$ gates on $n$ inputs have at most \[ (n+s+2)\left(16(n+s+2)^2\right)^s \] ordered descriptions: choose predecessors, a gate truth table, and an output wire. Circuits with fewer gates can be padded by projection gates. For fixed $s$ this is less than $2^{2^n}$ for sufficiently large $n$, so some $h$ has $C(h)>s$. This counting argument does not efficiently identify a hard table at the scale a reduction would need.

Could an address register retain the choice? If $p$ has $u$ stars, a table $F(z,x)$ displaying the completion selected by $z\in\{0,1\}^u$ has $2^{n+u}$ entries. Relative to input length $N=2^n$, polynomial output length requires $u=O(\log N)$, not $u=\Theta(N)$. Moreover restriction proves \[ C(F)\ge\max_z C(F|_z), \] not the minimum over $z$. Computing every completion reverses the existential quantifier in $C^*(p)$.

An edit-distance estimate for future gap gadgets.

Suppose $f,g$ differ on exactly $k\ge1$ rows $E$. For each $a\in E$ compute \[ e_a(x)=\bigwedge_{i=1}^n \begin{cases}x_i&a_i=1,\\ \neg x_i&a_i=0. \end{cases} \] Share the $n$ negated inputs; each conjunction uses $n-1$ gates, the disjoint indicators can be joined by $k-1$ OR gates, and $g=f\mathbin{\oplus}\bigvee_{a\in E}e_a$ uses one final binary gate. Reversing the roles of $f,g$ proves \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-34-3a-65-64-69-74} |C(f)-C(g)|\le n+k(n-1)+(k-1)+1=n(k+1). \end{equation} For $k=0$ the difference is zero. A fixed complete basis gives the bound $c_{\mathcal B}n(k+1)$ by a fixed gate simulation.

Consequently, if a proposed reduction has a proved yes-bound $a(m)$ and no-bound $b(m)$ before a correction of at most $k(m)$ table entries, its gap survives whenever \[ b(m)-a(m)>2c_{\mathcal B}n(m)(k(m)+1). \] The corrected bounds are respectively $a+c_{\mathcal B}n(k+1)$ and $b-c_{\mathcal B}n(k+1)$; an integer threshold strictly below the latter and at least the former works. This gives a concrete error budget, but neither the initial gap nor a suitable correction algorithm. On $p_h$, the complexity of the unspecified mask is exactly the uncontrolled quantity.

Repetition supplies no automatic amplification. If $F(z,x)=f(x)$, ignoring $z$ and restricting it give $C(F)=C(f)$ in the auxiliary convention. Repeating the same table expands output length but does not multiply complexity. XOR of two identical slices is constant.

Stress test and dependency check.

These are failures of specified transformations, not barriers against every reduction. A many-one reduction need not recover a satisfying assignment from every small circuit: imposing that would demand an additional witness-preservation property. The conditional obstruction to certain Levin reductions recorded by the 2026 source concerns a gap problem and extra assumptions, not an unconditional impossibility theorem for this exact question. [S1]

Membership in NP is unaffected by binary encoding of a huge bound $s$. Every $N$-entry table has a decision-tree circuit of $O(N)$ gates. Bounds above that universal ceiling are automatically yes; otherwise a circuit certificate uses $O(N\log N)$ bits and is checked on all $N$ rows in polynomial time. Neither this observation nor NP-hardness by itself separates $\mathsf P$ from $\mathsf{NP}$.

The companion script checks the completion and edit identities on all three-bit truth tables. These are finite Boolean checks, not circuit lower bounds. Equation (30006744:edit) and the counting proof apply at every length without relying on the experiment.

Outcome.

Outcome: Exploratory approach with unresolved gap. The attempt isolates two quantifier failures in partial-to-total encodings and proves an edit budget for a possible robust gadget. A polynomial-output deterministic transformation whose unrestricted minimum circuit sizes separate satisfiable from unsatisfiable instances is still missing. No such hardness reduction or counterexample to its existence is established.

Sources

• S1 Halley Goldberg, Mandar Juvekar, and Valentine Kabanets, Non-Levin NP-Hardness of Implicit MCSP and PAC Learning under Few Assumptions, ECCC TR26-091, Introduction, printed p. 3 $2026$. https://eccc.weizmann.ac.il/report/2026/091/download/. Catalogue formulation source.
• E1 S. Hirahara and R. Ilango, NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions, FOCS 2025, 1648--1664, abstract and introduction. https://www.rahulilango.com/papers/MCSP-Proceedings-2025.pdf. Conditional quasipolynomial-time nonadaptive hardness; not the target deterministic polynomial-time many-one reduction.