The Natural Proofs Barrier

We have spent decades believing that problems like SAT are intractable — that no small, fast circuit can solve them. Believing is easy. Proving it is the wall behind P vs NP, and we have barely scratched it.

The strange part is how the proofs fail. They don't fail randomly. Again and again, the most natural strategy is the same: find a simple, computable property that all "easy" functions share and the target function lacks. Show your function is too complicated to be easy, and you're done.

In 1994, Alexander Razborov and Steven Rudich proved something startling about that strategy. Any proof "natural" enough — broad and constructive in a precise sense — would not just separate hard problems. It would hand you a machine that breaks the pseudorandomness all of modern cryptography depends on. The very generality that makes the method work is what makes it self-destruct.

A "natural proof" needs a test — a property you can run on a function's truth table that says this function is too complex to be easy. For the proof to work, the test must accept almost all functions (most functions really are complex) and it must be efficient to evaluate.

Below, you build exactly such a test and then run it against two things: a genuinely random function, and a pseudorandom function that is secretly easy to compute. Watch what happens.

<p class="hint">{{hint}}</p>

<div class="controls">
  <label><input type="checkbox" id="balance" checked> {{label_balance}}</label>
  <label><input type="checkbox" id="autocorr" checked> {{label_autocorr}}</label>
</div>

<div class="cards">
  <div class="card" id="card-easy">
    <h4>{{card_easy_title}}</h4>
    <div class="tt" id="tt-easy"></div>
    <div class="verdict" id="v-easy">—</div>
    <small>{{card_easy_desc}}</small>
  </div>
  <div class="card" id="card-rand">
    <h4>{{card_rand_title}}</h4>
    <div class="tt" id="tt-rand"></div>
    <div class="verdict" id="v-rand">—</div>
    <small>{{card_rand_desc}}</small>
  </div>
  <div class="card" id="card-prf">
    <h4>{{card_prf_title}}</h4>
    <div class="tt" id="tt-prf"></div>
    <div class="verdict" id="v-prf">—</div>
    <small>{{card_prf_desc}}</small>
  </div>
</div>

<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reseed" type="button" class="ghost">{{btn_reseed}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .35rem; margin: 0 0 .8rem; font-size: .88rem; }
.controls label { cursor: pointer; }
.cards { display: grid; grid-template-columns: repeat(3, 1fr); gap: .6rem; }
.card { border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem; background: #f7fafc; }
.card h4 { margin: 0 0 .4rem; font-size: .92rem; color: #1d3557; }
.card small { display: block; margin-top: .4rem; color: #5a7088; font-size: .72rem; line-height: 1.3; }
.tt { display: grid; grid-template-columns: repeat(8, 1fr); gap: 2px; }
.bit { aspect-ratio: 1; border-radius: 2px; background: #dce4ea; }
.bit.on { background: #1d3557; }
.verdict { margin-top: .45rem; font-weight: 700; font-size: .82rem; min-height: 1.3em; }
.verdict.easy { color: #c92f3c; }
.verdict.complex { color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.4em; line-height: 1.4; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Here is the trap. Your test is supposed to reject easy functions. But a good pseudorandom function looks random to any efficient test — so your test accepts it, calling it "complex" even though it is built from a tiny, fast circuit. The moment your test is both useful (rejects easy functions) and general (efficient, accepts most functions), it becomes a distinguisher that tells pseudorandom from random. And that is exactly the tool cryptography assumes nobody has.

What exactly did Razborov and Rudich prove? Their 1994 paper (journal version 1997, Gödel Prize 2007) defines a proof of a circuit lower bound as natural when the property it uses to certify hardness has two features:

• Largeness — the property holds for most functions, not a rare handful. (It must, since most functions genuinely are hard.)
• Constructivity — given a function's truth table of size N = $2^{n}$, you can check the property in time polynomial in N.

Their theorem: if cryptographically strong pseudorandom functions exist, then no natural property can distinguish easy functions from hard ones. A constructive, large property is, by definition, an efficient test that most functions pass and easy functions fail — which is precisely a distinguisher that separates pseudorandom outputs from truly random ones. But pseudorandom functions are built from small circuits, so they are "easy," yet they must pass any efficient test. Contradiction.

The status is sharp: this is a conditional barrier, not an impossibility theorem. It does not say P vs NP is unprovable. It says that the broad, "obvious" style of argument — the kind that powered earlier circuit lower bounds — cannot reach it unless the discrete log-style hardness behind modern cryptography is false. Any successful proof must be un-natural: it must use some special structure of the target problem that does not generalize to most functions.

A barrier sounds like bad news, but knowing which roads are dead ends is how a field makes progress:

• It redirects research. Since 1994, people deliberately hunt for non-natural arguments — ones that fail the largeness or constructivity test on purpose, like Ryan Williams's 2011 lower bounds that use special algorithmic structure.
• It links two worlds. The barrier is a bridge: the more you believe cryptography is secure, the less you can rely on natural proofs. Hardness for the cryptographer is a handicap for the lower-bound prover.
• It is one of three great walls. Relativization (1975), natural proofs (1994), and algebrization (2008) together map out the proof techniques we know are too weak for P vs NP.
• It teaches a meta-lesson. Sometimes the obstacle to solving a problem is that our tools are secretly tools for something else — here, for breaking codes.

Understand this barrier and you understand why progress on P vs NP is slow not for lack of effort, but because the easy weapons are provably blunt.

The natural proofs barrier is one of the most beautiful pieces of self-reference in mathematics. It says: the cleaner and more general your method of proving "this is hard," the more surely it doubles as a key that unlocks cryptography. A technique broad enough to win is broad enough to self-destruct.

So the search for a proof that P vs NP goes on — but it must be un-natural, exploiting some quirk of the specific problem that refuses to generalize. The wall Razborov and Rudich built does not say we will never get there. It says that whatever gets us there will not look like anything we have tried before, and that is, in its own way, a clue.