Minimum Circuit Size Problem

A complete yes-or-no table lists a rule’s answer for every setting of its input switches. For two switches, the rule “yes only when both are on” has answers 0,0,0,1 at settings 00,01,10,11. A single AND gate reproduces it. The minimum circuit size problem asks whether a given table has any circuit within a stated gate budget. Its open classification question is whether deciding whether a circuit exists within the budget is as hard as every problem whose proposed answers can be checked efficiently.[1]

A yes-or-no rule is presented by its complete table of outputs, and the task is to decide whether a circuit of at most a specified size computes it. Is this ordinary decision problem NP-complete: as hard as every decision problem whose proposed answers have efficiently checkable certificates? The required polynomial-time many-one reduction turns one source instance into one target instance, preserving its yes-or-no answer. Fix a circuit convention: the cited paper uses two-input AND and OR gates and NOT gates, counting AND and OR gates while treating NOT gates as free. The two-input AND table has size one in this convention; size zero is impossible because inputs, constants and NOT operations alone cannot combine information from both switches.

With $n$ switches, the table has $N=2^n$ entries. Verification evaluates a proposed circuit on all $N$ settings, so its running time can be polynomial in table length even though it is exponential in $n$. Every Boolean table has a circuit of size polynomial in $N$, for example by listing the input settings that give one and combining their tests. Thus a yes instance has a certificate of polynomial length in the supplied table size. This explains membership in NP; it does not establish NP-hardness.[1]

A proposed circuit can be checked against every entry of the supplied table. That does not give an efficient way to find a small circuit or prove none fits the budget. A March 2025 result makes a related problem hard when a shared random lookup function is available; it does not settle the ordinary problem without that extra resource.[1]

Ilango’s March 2025 revision proves hardness in a model with a random oracle: each distinct query receives an independently chosen fair bit, and repeated queries receive the same answer. In the uniform formulation both the reduction and the target circuits have oracle access. This is not a proof that ordinary circuit-size instances are NP-complete. Replacing the ideal oracle by a real hash function is a proposed route, not a proved substitution in the theorem.[1]

A long table may conceal a short reusable computation. Recognizing that structure would tell us when an exhaustive list can be replaced by a compact implementation. The question also separates being able to run a simple rule from being able to discover that one exists.[1]

Compact implementation and recognition can have very different costs: evaluating a tiny circuit is easy once it is supplied, while inferring its existence from all outputs may be hard. The primary paper’s background also connects circuit-size recognition to average-case learning and cryptography. In particular, a polynomial-time algorithm for ordinary MCSP would rule out one-way functions, which are easy to compute but hard to invert on average in the relevant complexity sense. The random-oracle hardness result does not itself settle those ordinary cryptographic consequences.[1]