The Natural Proofs Barrier

In the circuit complexity video, we proved that parity cannot be computed by constant-depth circuits of polynomial size. That was a genuine separation, an unconditional lower bound, proved by concrete combinatorial techniques.

The obvious next step is to push harder: prove SAT needs large circuits of any depth. That would show SAT is not in P/poly, which is even stronger than $P\ne NP$, since $P$ sits inside P/poly. This was the program. For a while, it looked like it was working.

In 1994, Razborov and Rudich explained why it stopped.

The pattern behind every lower bound#

Look at how the parity lower bound works. You identify a combinatorial property of Boolean functions, in this case high average sensitivity. You show that parity has the property, and that no function computed by a polynomial-size constant-depth circuit does. The two facts together give the lower bound.

At the time, every known lower bound against nonmonotone circuits followed the same pattern. Razborov and Rudich gave it a name, a natural proof, and identified three conditions that make such a proof work: the property must be constructive, large, and useful.

Constructive#

A Boolean function on $n$ variables has a truth table with $2^n$ entries. Think of the combinatorial property as a test you run on this truth table. Constructivity means the test runs in time polynomial in the truth table size, that is, polynomial in $2^n$.

This is exponential in $n$, but the truth table itself is exponentially large, so relative to what you are looking at, polynomial time is reasonable. Constructivity is a generous condition: given the complete truth table, you can check the property without exhaustive search over all possible circuits or proofs. In the parity lower bound, checking high average sensitivity amounts to scanning the truth table and comparing nearby entries, well within the budget.

Large#

The property must be satisfied by at least a $2^{-O\left(n\right)}$ fraction of all Boolean functions on $n$ variables. A randomly chosen function should have a non-negligible chance of satisfying it.

Why should hardness be common? Shannon proved by counting that almost every Boolean function requires exponentially many gates, so any property that captures hardness should apply to most functions. Largeness also means the property is not picking out the target function by name; it identifies a structural feature shared by a non-negligible fraction of all functions.

Useful#

Any sequence of functions satisfying the property, one for each input length, must eventually require superpolynomial-size circuits. This is the condition that turns the property into a lower bound tool.

A natural proof against P/poly combines all three. It gives you a test, efficient on truth tables and satisfied by many functions, such that passing the test guarantees the function has no polynomial-size circuits. Apply the test to SAT. It passes. Lower bound proved.

Razborov and Rudich surveyed the known lower bounds. The $A{C}^0$ lower bounds of Furst, Saxe, and Sipser, of Yao, and of Håstad; Smolensky's bounds against $A{C}^0$ with modular counting gates, once his algebraic argument is carefully recast in combinatorial terms; the switching network bounds, the perceptron bounds, the formula size bounds: all natural. The framework captured the entire field.

The cryptographic ingredient#

Whether these techniques can reach P/poly depends on a seemingly unrelated idea from cryptography. A one-way function is easy to compute but hard to invert; multiplication of large primes is a standard candidate. From any one-way function you can build a pseudorandom generator, and from that a pseudorandom function generator, a construction due to Goldreich, Goldwasser, and Micali.

A pseudorandom function generator takes a short random seed and produces a Boolean function that no polynomial-size circuit can distinguish from a truly random function. The key point: the generated function is computed by a small circuit, since it is built from the seed by an efficient process, yet it looks random to any efficient test.

The proof defeats itself#

Suppose a natural proof against P/poly exists. Follow what happens.

The property is constructive, so there is a circuit of size polynomial in $2^n$ that tests whether a function has the property. The property is large, so a truly random function almost certainly satisfies it. Now take a pseudorandom function, produced by a generator from a short seed. The test circuit has size polynomial in $2^n$, and the generator is designed to fool circuits of size polynomial in $2^n$, so the test cannot distinguish the pseudorandom function from a truly random one. Since random functions satisfy the property, the test says the pseudorandom function satisfies it too.

But the pseudorandom function has a small circuit, and usefulness says any function with the property does not. Contradiction.

The natural proof is itself a statistical test that distinguishes easy functions from random ones, and pseudorandom function generators are built to make exactly that kind of test impossible.

The theorem: if pseudorandom function generators secure against circuits of size $2^{n^{ϵ}}$ exist, then no natural proof can establish superpolynomial lower bounds against P/poly. The contrapositive gives the result its force. A natural proof against P/poly would break every subexponentially secure pseudorandom function generator, and with it the subexponentially secure one-way functions underlying public-key cryptography, digital signatures, and secure communication. The assumption that makes cryptography possible is the same one that makes natural proofs impossible.

Pause and try: the parity proof is natural. Why doesn't it break any cryptography?

Run the self-defeating argument against $A{C}^0$ instead of P/poly. The natural property from the parity proof would distinguish functions computed by small constant-depth circuits from random functions. For a contradiction you would need a pseudorandom function generator whose outputs are computable in $A{C}^0$. But $A{C}^0$ is too weak to compute pseudorandom functions, so no cryptographic assumption is threatened. The barrier only bites once the circuit class is strong enough to compute its own camouflage, and P/poly is.

Lower bounds are upper bounds#

Razborov and Rudich put it this way: any natural lower bound proof must implicitly argue a proportionately strong upper bound. The proof that a function is hard simultaneously hands you an algorithm that breaks the pseudorandomness of the class you attacked. The barrier therefore bites only at a certain level of circuit power: $A{C}^0$ cannot compute pseudorandom functions, so natural proofs work fine there, while P/poly is strong enough to contain them. The more powerful the circuit class, the better it defends itself against natural attacks.

What slips through#

The barrier rules out proofs that are both constructive and large. Violate either condition and it does not apply.

A proof that applies to only a negligible fraction of functions, identifying its target by construction rather than by a shared property, is not large. Diagonalization arguments work this way; they built the time hierarchy theorem, and the barrier does not touch them. A proof whose property takes superpolynomial time to check on truth tables is not constructive; such a proof could exist, but no one has found a way to use one.

Razborov and Rudich also observed that the discrete logarithm, a specific function believed to be hard, lies in the image of a concrete pseudorandom generator, so no natural proof can establish exponential circuit lower bounds for it, regardless of what cryptographic assumptions you make.

And in 2010, Ryan Williams proved that NEXP is not contained in $AC{C}^0$ using a technique that is not fully natural. His proof connects faster algorithms for circuit satisfiability to circuit lower bounds, targeting a specific function by an indirect diagonalization rather than a shared combinatorial property, which avoids largeness. Williams later proved something striking: any proof that NEXP avoids a typical circuit class must satisfy constructivity and usefulness. Largeness is the one condition you can dodge. The gap in the wall is real, but it is narrow.

The shape of the wall#

In the history of complexity video we saw the relativization barrier: a proof that treats computation as a black box cannot resolve P versus NP. Now we have the natural proofs barrier: a proof that tests truth tables for a shared combinatorial property cannot resolve it either, assuming cryptography is sound. The barriers do not say the question is unanswerable. They say the answer requires techniques that are non-relativizing, non-natural, or both.

The hardness we want to prove is the very thing that shields the problem from our proofs. If $P$ really differs from $NP$, the functions that witness the difference can hide among random functions, indistinguishable by any efficient test. The proof that they are hard must see something that circuits cannot.

If you remember three things#

1. A natural proof tests truth tables for a property that is constructive, large, and useful. Every nonmonotone circuit lower bound known in 1994 fit the pattern.
2. If pseudorandom function generators exist, no natural proof can prove superpolynomial lower bounds against P/poly: the proof would itself be the distinguisher that breaks them.
3. The escape routes are to drop largeness or constructivity. Williams's NEXP versus $AC{C}^0$ result threads the largeness gap, and that gap is the only one known to be passable.