Math Conjectures

NP-Hardness of the Minimum Circuit Size Problem

OPENMajorOpen problemProposed c. 1975 · Standard version

Canonical statement

The Minimum Circuit Size Problem (MCSP) takes as input the N=2nN=2^n-bit truth table of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} and an integer s≤Ns\leq N, and asks whether ff has a Boolean circuit over the fixed complete basis {AND,OR,NOT}\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}, with AND\mathsf{AND} and OR\mathsf{OR} of fan-in two, and with at most ss gates. Is MCSP NPNP-hard under deterministic polynomial-time many-one reductions?
View source LaTeX
The Minimum Circuit Size Problem (MCSP) takes as input the
\(N=2^n\)-bit truth table of a Boolean function
\(f:\{0,1\}^n\to\{0,1\}\) and an integer \(s\leq N\), and asks whether
\(f\) has a Boolean circuit over the fixed complete basis
\(\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}\), with
\(\mathsf{AND}\) and \(\mathsf{OR}\) of fan-in two, and with at most
\(s\) gates. Is MCSP \(NP\)-hard under deterministic polynomial-time
many-one reductions?
TCS-025:[AllenderEtAl2006MCSP][MurrayWilliams2017MCSP][Hirahara2020MCSP]
Theoretical computer scienceLogic and foundations

Notes

The Minimum Circuit Size Problem (MCSP) takes the full 2n2^n-bit truth table of a Boolean function together with a threshold ss, and asks whether some circuit with at most ss gates over the basis {AND,OR,NOT}\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\} computes the function. A candidate circuit can be checked against the truth table, so MCSP lies in NPNP; the question is whether it is NPNP-hard under deterministic polynomial-time many-one reductions. The modern formulation emerged around 1975, with no single documented first proposal.

MCSP sits at a crossroads of complexity theory, tied to natural properties, pseudorandomness, and the power of random strings [AllenderEtAl2006MCSP]. Murray and Williams studied the (non-)NPNP-hardness of computing circuit complexity, clarifying obstacles to proving hardness under standard reductions [MurrayWilliams2017MCSP]. Hirahara's non-black-box worst-case to average-case reductions within NPNP further connect MCSP-style problems to average-case complexity [Hirahara2020MCSP].

Hardness is known for variants and under restricted or otherwise nonstandard reductions, but ordinary many-one NPNP-hardness — or a proof that it fails — remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.