Introduction

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.

The Self-Destructing Test

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">A <b>natural proof</b> needs a cheap <b>test</b> that flags a function as "too complex to be easy." A useful test must <b>reject easy functions</b> and <b>accept most functions</b>. Build the test, then run it on three truth tables.</p>

<div class="controls">
  <label><input type="checkbox" id="balance" checked> Balance check (≈ half the outputs are 1)</label>
  <label><input type="checkbox" id="autocorr" checked> Pattern check (no obvious repeating structure)</label>
</div>

<div class="cards">
  <div class="card" id="card-easy">
    <h4>Easy function</h4>
    <div class="tt" id="tt-easy"></div>
    <div class="verdict" id="v-easy">—</div>
    <small>A tiny circuit: output 1 on the first half.</small>
  </div>
  <div class="card" id="card-rand">
    <h4>Random function</h4>
    <div class="tt" id="tt-rand"></div>
    <div class="verdict" id="v-rand">—</div>
    <small>Truly random bits — genuinely hard.</small>
  </div>
  <div class="card" id="card-prf">
    <h4>Pseudorandom function</h4>
    <div class="tt" id="tt-prf"></div>
    <div class="verdict" id="v-prf">—</div>
    <small>A small keyed circuit — secretly easy.</small>
  </div>
</div>

<div class="status" id="status">Press "Run the test".</div>
<div class="btns">
  <button id="run" type="button">Run the test</button>
  <button id="reseed" type="button" class="ghost">New random seed</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; }

// The natural proofs barrier (Razborov & Rudich, 1994). A "natural property" is a
// cheap test on a function's truth table that is LARGE (most functions pass) and
// CONSTRUCTIVE (efficient to evaluate), used to certify a function is "too complex
// to be easy". The catch: such a test is exactly a DISTINGUISHER. A pseudorandom
// function is built from a tiny circuit (so it is EASY) yet looks random to any efficient test, so the test wrongly accepts it as "complex" — self-destructing.
const N = 64;            // truth table size = 2^6
let seed = 1234567;
function rng(){ seed = (seed*1103515245 + 12345) & 0x7fffffff; return seed / 0x7fffffff; }

// EASY: output 1 on the first half. Highly structured, tiny circuit.
function easyFn(){ const t=[]; for(let i=0;i<N;i++) t.push(i < N/2 ? 1 : 0); return t; }
// RANDOM: truly random bits. Genuinely hard (no small circuit, w.h.p.).
function randFn(){ const t=[]; for(let i=0;i<N;i++) t.push(rng()<0.5?1:0); return t; }
// PRF: keyed scramble — deterministic, computed by a small circuit, but well-mixed.
function prfFn(key){ const t=[]; for(let i=0;i<N;i++){
  let x = (i ^ key) >>> 0; x = (x*2654435761) >>> 0; x ^= x>>>13; x = (x*40503) >>> 0; x ^= x>>>7;
  t.push(x & 1); } return t; }

// ── The "natural test": cheap statistics. Returns true = "looks COMPLEX" (accept). ──
function balanceOk(t){ const ones=t.reduce((a,b)=>a+b,0); return Math.abs(ones - N/2) <= N*0.18; }
function patternOk(t){ // low autocorrelation at shift 1: structured tables score high
  let same=0; for(let i=0;i<N;i++) if(t[i]===t[(i+1)%N]) same++;
  return Math.abs(same - N/2) <= N*0.22; }
function naturalTest(t){
  const useBal = document.getElementById('balance').checked;
  const usePat = document.getElementById('autocorr').checked;
  let complex = true;
  if(useBal) complex = complex && balanceOk(t);
  if(usePat) complex = complex && patternOk(t);
  return complex; // true = test calls it "complex" (accepts as hard)
}

function drawTT(id, t){ const el=document.getElementById(id); el.innerHTML='';
  for(let i=0;i<N;i++){ const d=document.createElement('div'); d.className='bit'+(t[i]?' on':''); el.appendChild(d); } }
function verdict(id, complex){ const el=document.getElementById(id);
  if(complex){ el.textContent='✓ test says: COMPLEX'; el.className='verdict complex'; }
  else { el.textContent='✗ test says: easy'; el.className='verdict easy'; } }

let TE, TR, TP;
function build(){ TE=easyFn(); TR=randFn(); TP=prfFn(0x9e37); drawTT('tt-easy',TE); drawTT('tt-rand',TR); drawTT('tt-prf',TP);
  ['v-easy','v-rand','v-prf'].forEach(i=>{const e=document.getElementById(i); e.textContent='—'; e.className='verdict';}); }

function run(){
  const ce=naturalTest(TE), cr=naturalTest(TR), cp=naturalTest(TP);
  verdict('v-easy',ce); verdict('v-rand',cr); verdict('v-prf',cp);
  const s=document.getElementById('status');
  if(!ce && cr && cp){
    s.textContent='Your test rejected the easy function and accepted the random one — useful! But it ALSO accepted the pseudorandom function, which is secretly easy. Your test just became a distinguisher: it breaks cryptography.';
    s.className='status bad';
  } else if(ce){
    s.textContent='Now your test even accepts the obviously-easy function — it is no longer useful as a hardness certificate.';
    s.className='status bad';
  } else {
    s.textContent='Weaken the test enough to fool nobody and it stops rejecting easy functions. There is no escape: any large + constructive test is a distinguisher.';
    s.className='status';
  }
  console.log('easy complex?',ce,'| random complex?',cr,'| PRF complex?',cp);
}

document.getElementById('run').addEventListener('click',run);
document.getElementById('reseed').addEventListener('click',()=>{ seed=(Date.now()%2000000000)+1; build(); document.getElementById('status').textContent='New seed — press "Run the test".'; document.getElementById('status').className='status'; });
document.getElementById('balance').addEventListener('change',()=>{document.getElementById('status').textContent='Test changed — press "Run the test".';document.getElementById('status').className='status';});
document.getElementById('autocorr').addEventListener('change',()=>{document.getElementById('status').textContent='Test changed — press "Run the test".';document.getElementById('status').className='status';});
build();
Result
Console

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.

The Real Barrier

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 = 2n2^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/natural-proofs/Content licensed under CC BY-NC 4.0.