The Natural Proofs Barrier and Why Circuit Lower Bounds Stall

Every lower bound in this cluster follows the same template. Define a property that every function with a small circuit lacks, show that the target function has the property, conclude that the target is hard. The switching lemma uses “cannot be approximated by a small-width formula”. The polynomial method uses “cannot be approximated by a low-degree polynomial”. The counting argument uses “has a truth table that no small circuit can match”. Razborov and Rudich asked what all these properties have in common, and the answer they found is a barrier rather than a technique.

The three conditions

A property $\mathcal{P}$ of Boolean functions is a set of functions on $n$ variables, identified with their truth tables, so $\mathcal{P} \subseteq {0,1}^{2^n}$.

$\mathcal{P}$ is natural with respect to a size bound $s(n)$ and a circuit class if it satisfies three conditions.

It is useful: no function in $\mathcal{P}$ has a circuit of size $s(n)$. This is what makes the property a lower bound. It is a statement about the class of small circuits, not about any particular function.

It is large: at least a $2^{-O(n)}$ fraction of all $2^{2^n}$ functions belong to $\mathcal{P}$. The counting argument’s property — “needs more than $s$ gates” — is large by construction, since the fraction of functions with small circuits is at most $2^{2^n}/2^{2^n} \cdot$ (a vanishing factor).

It is constructive: membership in $\mathcal{P}$ can be decided from the truth table in time polynomial in the table length $2^n$, that is, in time $2^{O(n)}$. The switching-lemma property is constructive, because checking whether a function has a small-width formula can be done by examining its truth table; the low-degree property is constructive, because the degree over a finite field is computable by linear algebra on a $2^n \times 2^n$ matrix.

def is_large_and_useful(table, size_bound):
    """table: bytes of length 2^n, one bit per input.
    Sketch only: the real test needs the circuit class, not just a size bound."""
    n = len(table).bit_length() - 1
    # 'Useful' is a statement about the best circuit, not about this table.
    # A test that runs in poly(2^n) can only inspect global statistics.
    ones = sum(bin(b).count('1') for b in table)
    return ones, n          # e.g. bias is a large, constructive property

Why the conjunction is fatal

The theorem: if there is a natural property useful against circuits of size $s(n) = 2^{n^{\epsilon}}$ for some $\epsilon > 0$, then there is no pseudorandom function generator with seed length $n$ and output length $2^{n^{\epsilon}}$ that is secure against circuits of size $2^{n^{\epsilon}}$.

The argument is short and it uses each condition exactly once.

Suppose a natural property $\mathcal{P}$ exists, and suppose a pseudorandom function generator $G$ exists with the stated parameters. A pseudorandom function is indistinguishable from a random function by small circuits. But $\mathcal{P}$ is constructive and large: a circuit of size polynomial in $2^n$ can test membership in $\mathcal{P}$, and since $\mathcal{P}$ contains a $2^{-O(n)}$ fraction of all functions, a random function is in $\mathcal{P}$ with probability at least $2^{-O(n)}$. The distinguisher samples a function from $G$‘s output distribution and tests membership in $\mathcal{P}$: functions from $G$ are, by usefulness, outside $\mathcal{P}$ — because a function with a small circuit cannot be in a property that is useful against small circuits, and $G$‘s outputs are computable by circuits of size $2^{n^{\epsilon}}$, which is within the useful range. So the distinguisher accepts random functions with probability at least $2^{-O(n)}$ and accepts pseudorandom ones with probability zero. The gap is small but nonzero, and it is enough: a distinguisher that separates the two distributions with any non-negligible advantage breaks the generator.

The parameters matter. The distinguisher runs in time polynomial in $2^n$, which is exponential in the seed length $n$ — that is exactly the security parameter, so the distinguisher is not efficient in the cryptographic sense. The contradiction is with a generator secure against circuits of size $2^{n^{\epsilon}}$, not against polynomial-size circuits. That is why the barrier’s conclusion is conditional: it rules out natural proofs of strong circuit lower bounds, and it says nothing about weak ones.

What the theorem actually forbids

The conclusion is usually stated as: if factoring, discrete logarithm, or any of the standard number-theoretic problems is hard for subexponential circuits, then no natural proof can separate $\mathrm{P}$ from $\mathrm{NP}$.

The chain from the barrier to that statement runs through the existence of pseudorandom functions. A one-way function with subexponential hardness yields a pseudorandom function generator by the GGM construction, with seed length $n$ and output length polynomial in $n$; amplifying the output length to $2^{n^{\epsilon}}$ requires a stronger assumption, but the standard assumption that factoring is hard for $2^{n^{\epsilon}}$-size circuits supplies it. So under that assumption, a natural proof of $\mathrm{P} \ne \mathrm{NP}$ cannot exist.

Three things are worth separating in that statement.

It is not a proof that $\mathrm{P} \ne \mathrm{NP}$ is unprovable. It is a proof that a particular class of argument cannot prove it, under a particular hardness assumption. A non-natural proof would escape.

It does not say the assumption is true. The barrier is conditional, and if factoring turned out to be easy, the barrier would evaporate along with the pseudorandom functions.

It does not apply to lower bounds against weak circuit classes. The usefulness condition is about circuits of size $2^{n^{\epsilon}}$, and a property useful only against, say, $\mathrm{AC}^0$ circuits is not useful in the sense the theorem needs. This is why the switching lemma and the polynomial method survive: they are natural with respect to restricted classes, and the barrier’s hypothesis requires usefulness against general circuits of near-exponential size.

Which known proofs are natural, and which are not

The inventory is instructive, because it shows the barrier cutting across the cluster.

Natural: the counting argument. Its property is large and constructive — the truth table is checked against all small circuits, which takes time exponential in $n$ and is therefore allowed. It is useful against circuits of size up to $2^n/n$, which is within the barrier’s range. The counting argument is the archetype the barrier was designed to describe, and its inability to name a hard function is the informal version of the theorem.

Natural: the switching lemma and the polynomial method, in their restricted forms. Each defines a property that is large, constructive, and useful against the restricted class. Neither is useful against general circuits, which is why neither is blocked — the barrier does not forbid a proof that only works against a subclass.

Not natural: the monotone lower bounds. Razborov’s approximation method is useful against monotone circuits, and its property — “far from every monotone function of low complexity under a distribution” — is not obviously constructive in the required sense, because it depends on a distribution tailored to the function. More importantly, the property is not large: it says nothing about general circuits, and the monotone restriction is what makes the argument work. Razborov’s later analysis showed that extending the method to general circuits would give a factoring algorithm, which is the monotone-specific form of the same obstruction.

Not natural, and the only known escape is the Williams argument, which shows that $\mathrm{NEXP} \not\subseteq \mathrm{ACC}^0$ without exhibiting a property of functions at all. It shows that if $\mathrm{ACC}^0$ contained $\mathrm{NEXP}$, a satisfiability algorithm for $\mathrm{ACC}^0$ circuits would contradict the nondeterministic time hierarchy. The contradiction is algorithmic, not combinatorial, and the barrier’s three conditions have no purchase on it.

The barrier as a guide rather than a wall

Two practical consequences follow, and they shape how lower-bound work is organised.

The first is that progress has moved toward restricted models. Every unconditional result in this cluster is a statement about a class smaller than general polynomial-size circuits: constant depth, monotone gates, bounded formula size, block-respecting structure. The depth hierarchy is the map of those results, and its unresolved middle — $\mathrm{TC}^0$ versus $\mathrm{NC}^1$ — is precisely the point where the natural techniques run out and no non-natural one has replaced them.

The second is that hardness assumptions and lower bounds are two sides of one coin. A pseudorandom function generator is, by definition, a function that small circuits cannot distinguish from random, and a circuit lower bound is a proof that a specific function is not computed by small circuits. The barrier says these two projects cannot both be pursued by the same method: a natural proof of hardness would destroy the pseudorandom objects that hardness is used to build. That tension is not a paradox, but it does mean that a successful general lower bound will have to look unlike anything in the current toolkit, and that the search for one is constrained in a way that no other area of complexity theory is.

The size of the gap, stated plainly

The best explicit lower bound for a function in $\mathrm{NP}$ over a complete basis is linear, around $3.1n$ gates; the counting bound says most functions need $2^n/n$. The natural proofs barrier explains why the gap has not closed by brute force: the properties that would close it are exactly the ones that a pseudorandom function generator is designed to evade, and the generator’s existence is assumed by most of cryptography. The barrier does not prove the gap is permanent, and it does not apply to algorithms that avoid defining a property of functions. It does establish that any proof of a superpolynomial lower bound must be non-natural, and that fact alone rules out the entire classical toolkit — counting, restriction, approximation, and degree — as a route to the general case.