Reuse and the Wall — why the lever that breaks problems cannot prove them unbreakable

Reuse is the cheapest way to break a hard problem. You don't grind the wall down; you find that the wall is a door someone already opened in another room, and you walk through with a borrowed key. Whole frontiers fall this way — a problem that resisted for centuries collapses in an afternoon once somebody shows it was secretly a problem we'd already solved, wearing a disguise.

So here is a strange thing. The same reuse that is a master lever for solving becomes, exactly, a wall when you turn it the other way and ask it to prove a problem unsolvable. Not by accident, and not from lack of cleverness. Three separate theorems in complexity theory say so, each ruling out a whole family of proof techniques for separating complexity classes — for proving, rigorously, that some problems are genuinely hard. They are called relativization, natural proofs, and algebrization. They are usually taught as three unrelated obstacles. They are not. They are one observation in three costumes.

The more universally a method can be reused, the less it can tell two things apart.

That sentence is the whole essay. A proof that some problem is hard has to discriminate — it has to detect the one specific structural fact that makes this problem hard and that problem easy. A technique general enough to be reused across every case, every world, every function is, by that very generality, blind to the particular difference it would need to see. Generality and discrimination trade against each other. The barriers are three precise prices on that trade.

Barrier one

Relativization · 1975Reuse across worlds

An oracle is a thought-experiment: a magic box bolted to a machine that answers one fixed question instantly, for free, no matter how hard that question normally is. You never see inside it. You hand it a question, it returns yes or no in a single step. The device lets you ask: if this one hard thing were free, would the rest of the difficulty melt — or stand?

A proof relativizes when its logic doesn't care what's in the box. Attach any oracle you like and the same argument still runs, because it only ever watches inputs and outputs — never the machinery. That is reuse in its purest form: a single argument, replayed identically in every possible world.

Baker, Gill and Solovay built two worlds. In one, an oracle is strong enough to absorb the entire gap between finding and checking — and in that world, the easy and hard classes coincide. In the other, an oracle is built so the gap survives intact. Both worlds are real and consistent. So a relativizing proof of hardness would have to deliver its verdict in both — and the verdicts are opposite. The same argument cannot be true in a world where the gap closes and a world where it doesn't.

The price: any technique that treats the machine as a black box and reuses itself across all oracles is too coarse to see a difference that depends on what's inside the box. It is blind by construction.

Barrier two

Natural proofs · 1994Reuse across the typical

This is the one that bites hardest, because it bites itself. Nearly every lower-bound proof we know works by finding a property of functions that is two things at once: efficiently checkable, and shared by most random functions — and that property is then shown to force any function carrying it to be hard. Razborov and Rudich named proofs of this shape natural, and proved a devastating thing about them.

If your property is efficiently checkable and common among random functions, you can reuse it as a distinguisher: a fast test that tells genuine randomness from the merely pseudo-random. But a fast distinguisher of that kind would break cryptography — including the factoring-based cryptography whose security is the assumption that certain problems are hard. So if hard problems really exist, no natural proof can prove it.

The hardness of the problem is part of what forbids the standard tools from proving the problem hard.

Read it as flatness. A reusable, checkable property is a way of detecting a gradient across the space of functions — a slope separating the hard from the easy. The natural-proofs barrier says that if cryptographic hardness is real, that space is flat to any efficient eye. The hard functions are the typical ones, indistinguishable from their neighbors. And you cannot detect a slope on a surface that has none.

The price: a property reusable across the typical case is exactly a crypto-breaking distinguisher. Its reusability is the weapon that turns against the very hardness you wanted to certify.

Barrier three

Algebrization · 2008Reuse across the lift

A few clever techniques seemed to slip past the first barrier — the arguments behind certain famous interactive-proof results did not relativize in the ordinary way. Aaronson and Wigderson asked a sharper question: do those techniques survive if you extend each oracle to its low-degree polynomial version — its algebraic lift?

Mostly, yes. And once again there are algebraic-oracle worlds on both sides of the question. So the techniques that dodged the black box still cannot separate the classes, because they remain reusable across the lift — and reusability across the lift is, one more time, blindness to the difference that lives below it.

The price: the same trade at a higher altitude. Survive the algebraic reuse, and you forfeit the power to discriminate. The third costume of the one idea.

The duality, stated plainly

Put the three together and a single shape stands out, and it is a shape about reuse:

Reuse is a lever for solving and a wall for proving-hard.

When you want to break a problem, reuse relocates you next to an answer someone already built — the cheapest, most general move there is. When you want to prove a problem unbreakable, you need the opposite of relocation: you need to detect the one structural fact that makes this instance hard. And a method general enough to be reused everywhere cannot, by its nature, be sensitive to anywhere in particular. The lever and the wall are the same tool, held at two ends.

There is a taxonomy hiding under this. Problems break open in a few primitive ways — you can connect (reduce, dualize, reuse), you can construct (forge a tool that did not exist), you can exhaust, you can dissolve a false premise. The cheap, common breaks are nearly all connect. The deep, celebrated, decades-resisting breaks are nearly all construct — someone stood at a wall with no key in existence and had to make one. The three barriers are a formal proof that a separation cannot come from connect. To get past all three you would need a technique that is non-relativizing, non-natural, and non-algebrizing at once: instance-sensitive, refusing to be reused. Not a borrowed key. A forged one.

Which is why the problem has resisted for half a century. Not bad luck. A theorem that the cheap primitive is disabled, and only the expensive one remains.

What this is, and is not This essay proves nothing new. It is a reading — a single lens laid over three results that belong entirely to their authors. The barriers do not say the classes can't be separated; they say a family of techniques can't do it, which is a map of exhausted ground, not a verdict of impossibility. Treat the reuse/difficulty framing as a way of seeing, offered in good faith, and the mathematics as the property of the people cited below.