October 9, 2026English
P vs NP: the ninja cat's guide to winning a million dollars
On 7 October 2026, Vitalik Buterin posted a thread on X that was read as a warning about quantum computing and was about something else. The topic was Justin Drake’s proposal to move into “bunker mode” and migrate funds to fresh addresses, in the face of a risk that AI-accelerated mathematics starts breaking lattice cryptography. And in the middle of the argument, almost in passing, comes the sentence that holds up everything else:
Theoretically, of course it’s possible that hashes are broken too (eg. P = NP would imply that). But I think P = NP is very unlikely. And intuitively, it’s much more likely that a mathematical object has exactly no exploitable structure (like hashes are intended to), than that a mathematical object has exactly three forms of exploitable structure and not some secret fourth form we have not yet discovered.
Buterin was not discussing the millennium problem. He was using it as the floor. And there is the oddity this article wants to look straight in the eye: the entire digital world is standing on a conjecture nobody can prove, betting that it is true. Every signature, every hash, every vault, every encrypted message you send in a day is a bet on P ≠ NP.
Six steps and nine panels, with a million dollars waiting inside a vault. The whole route can be walked believing that the story ends at “nobody knows, and if P = NP everything collapses”. It does not end there: the conjecture holding up the digital world is not the one cryptography needs, and that is what follows.
Step 1: P — what you can solve fast

P is the class of problems a computer can solve in polynomial time: the work grows in a reasonable way when the input grows. Sorting a list, multiplying two numbers, finding the shortest path on a map. Saying “fast” here is a mathematical promise about growth, not about seconds: one algorithm can be polynomial and still be a thousand times worse than another polynomial algorithm.
And it should be said from the start, because it is half of the misunderstanding: P is not “what computers can do”. It is what they can do in the worst imaginable case for each size. In practice there are NP-hard problems being solved every day: SAT solvers dispatch industrial instances with millions of variables, in hardware verification and planning. Theory talks about the worst case; engineering lives off the average case.
Step 2: NP — what you can verify fast

NP is the class of problems whose solution, once someone hands it to you, you can check fast. Sudoku: filling it in from scratch can take forever; looking at a completed grid and saying “yes, that’s valid” takes you a minute. The travelling salesman: finding the shortest route among fifty cities is hell; verifying that a proposed route measures what it claims does not.
And here comes the example that matters to us: factoring a huge number. Multiplying two thousand-bit primes is instant. Recovering those primes from the product is — as far as we know — impossible in practice. RSA, ECDSA, Diffie-Hellman, the signature you use to move money: all of it lives off that asymmetry.
With a precision that later on will be the key to this article: factoring is in NP and also in co-NP, and it is not known to be NP-complete. It is believed not to be. Keep that fact, because it is the one that breaks the optimistic story of “if P ≠ NP, my cryptography is safe”.
The diagnostic matrix

| Dimension | P | NP |
|---|---|---|
| Solve (produce the answer) | Easy and efficient | Terribly hard |
| Verify (check the answer) | Easy and efficient | Easy and efficient |
| The real world | Multiplying 15 × 15 | Breaking a bank’s security |
The table hides a trap: P is contained in NP. Anything you can solve fast, you can obviously verify fast. The million-dollar question is not whether P and NP differ in general — nobody doubts that — but whether they differ completely, or whether that difference is an illusion that evaporates once we find the right trick.
One number to size up the lock: the world factoring record (RSA-250, February 2020) reached 829 bits and cost roughly 2,700 CPU-years spread over tens of thousands of machines. RSA-2048 is still intact. The margin is not twofold: it is astronomical, and that is why we live calmly.
Step 3: the big question

The question is one sentence, and it is so simple it looks like a trick:
Can every problem whose solution can be verified fast also be solved fast?
P = NP means that verifying and solving are, at bottom, the same job. P ≠ NP means that genuinely hard problems exist: that there is an arrow you cannot turn around.
Steve Cook formulated it in 1971 and Leonid Levin in 1973, but the intuition is older: in 1956 Kurt Gödel wrote to John von Neumann wondering how many steps it would take to find a proof, compared with checking one. Nobody answered that letter. In 2000, the Clay Mathematics Institute put it on its list of seven Millennium Problems, with one million dollars each. Only one has been solved: Poincaré, in 2003. Grigori Perelman refused the prize.
Step 4: imagine the chaos

If P = NP were true, two worlds open at once.
The utopian branch is the one told on stage: perfect optimisation, instant drug design, protein folding, logistics, AI without a ceiling, mathematical proofs found by machine. Everything we today solve by brute force or by approximation would become exact.
The apocalyptic branch is the one that matters to us: RSA and elliptic curves fall, hashes fall, the signature on everything you have ever signed falls. There would be no “weaker privacy”: there would be no privacy. Any encrypted message stored today is a plaintext message of the future, because the attacker only has to wait for the algorithm to arrive.
Three nuances that usually get left out and that need to be said:
- The collapse does not have to be instant. A polynomial algorithm can be a polynomial with an absurd exponent: if the best algorithm for SAT runs in n^1000, your cryptography is still standing in practice. P vs NP asks about the shape of the curve, not about the clock.
- The proof might not give an algorithm. If someone proves P = NP non-constructively — by contradiction, or with an argument that does not produce the machine — they win the million and break nothing. It is a rare case but perfectly conceivable.
- Quantum computers are not a shortcut to P = NP. Shor (1994) breaks RSA and elliptic curves, yes, but because factoring has exploitable algebraic structure — not because quantum computing solves NP-complete problems. No NP-complete problem is known to be solvable in quantum polynomial time, and it is believed none is. Grover only gives a square-root advantage. Quantum computing does not threaten the scaffolding of P ≠ NP; it threatens it from another side.
The Vitalik case: hashes, lattices and the noise that actually matters

Let’s go back to the 7 October thread, because it carries a lesson in method. Buterin was not pointing at P = NP as the danger. On the contrary: he was saying that, for hashes, P = NP is the only real danger, and that for that very reason hashes are the most solid part of the ecosystem. A hash is designed to have no exploitable structure. And it is far more plausible that a mathematical object has no structure at all, than that a mathematical object has three forms of structure and none of them is hiding a fourth.
The danger he does see lies elsewhere: lattices (ML-DSA, FHE, lattice-based cryptography), the post-quantum cryptography everybody is adopting precisely because elliptic curves are going to fall. The argument, in his words, is the one about “skeletons in the closet”: factoring was believed hard until decades of smart mathematicians degraded it from 2^(n/2) to 2^O(n^(1/3)) and forced RSA keys to be 400 bytes instead of 64. What if there are improvements of that calibre, hidden for lattices, that we are not smart enough to find but a bot soon will be? His practical recommendation: for anything lattice-based, multiply key sizes by ten; and wherever possible, stay with hashes.
This does not contradict the rest of the article: it completes it. The concrete threat to cryptography today is not P = NP. It is real cryptanalysis, AI-assisted, against concrete hardness assumptions. And yet the place where the conversation always ends up is the same one: (eg. P = NP would imply that). It is the floor of the building, and we all know it is there.
The part that breaks the story: P ≠ NP is not enough
Here comes the point which in an article about sovereignty cannot be skipped.
P ≠ NP does not give you cryptography. Everything we use — hashes that cannot be inverted, signatures nobody can forge — rests on something sharper: one-way functions, that is, problems that are hard on average, not only in the worst case. And average-case hardness is a completely different world from the one P vs NP asks about.
Russell Impagliazzo told it in 1995 with an exercise that deserves a place in any curriculum: five possible worlds.
- Algorithmica: P = NP. Cryptography is impossible.
- Heuristica: P ≠ NP, but the hard problems are easy on average. Cryptography is impossible here too.
- Pessiland: average-case hard problems exist, but one-way functions do not. P ≠ NP is true and yet there is no cryptography of any kind. There are no pseudorandom generators either: the world is cold, deterministic and legible to anyone.
- Minicrypt: one-way functions exist. There are hashes, symmetric encryption, MACs. There is no public-key cryptography: no signatures, no key exchange, no blockchains.
- Cryptomania: one-way functions with a trapdoor exist. There is public-key crypto, there are signatures, there is digital money. This is the world we live in — or the one we assume we inhabit.
The lesson is that cryptography does not live off P ≠ NP. It lives off a finer bet: that worst-case hardness can be manufactured and carried all the way to your key, on average, with a distribution you control. And that bet is stronger than the other one: if one-way functions exist, then P ≠ NP (because inverting is verifying, and finding the preimage is solving). The converse is not known. That is: proving P ≠ NP would be a great advance in mathematics and not an insurance policy for your privacy.
And there is one more detail. Remember factoring: it is in NP and in co-NP, and it is not believed to be NP-complete. Which means the hardness of RSA does not follow from P ≠ NP even if tomorrow someone proves P ≠ NP in the most rigorous possible way. We live in a house with two foundations: a visible and revered one (P ≠ NP) and a real and far more fragile one (average-case hardness). When people talk about “provable security”, they are almost always talking about the first.
The key is also the door
“Bunker mode” can be summarised in one sentence: move your funds to fresh addresses that have never signed anything, so your public key stays hidden behind the hash of the address. The cryptography is right: if the public key was never revealed, there is nowhere to get the private one from — neither with quantum nor without it. The advice is solid for a treasure.
The problem is that in what we build, the key does not guard a treasure: it is a name.
At RHM Seguros the corporate email has no password: you sign in by connecting the wallet and signing a message with a nonce. In Ius and ChatWallet the identity is the key pair: the Ğ1 link standard we wrote is two crossed signatures declaring that an 0x… address and a g1… account are the same person, and that link lives on-chain. We sign to get in, to identify ourselves, to certify that someone is someone, so that another can read what we publish. If the address that identifies you has to stay virgin forever, you stop being able to sign — that is, you stop being able to be.
And moving is not free. In Ğ1 v1 a key was an identity: changing it meant revoking the identity and gathering five new certifications, with a two-month window and the patience of five people. In Duniter v2 — the one running Ğ1 since March 2026 — there is identity.changeOwnerKey: the identity survives the key change, but you sign the migration with the new key and it stays on-chain, with a window in which the old key can still revoke it. That is exactly the opposite of hiding behind a hash: it is a public act, with witnesses.
The answer is not to hide the key: it is to separate it. One key to sign, another to hold. That the one identifying you has no value, and that the one with value is almost never used. In the protocol this already exists (contracts with a hierarchy of keys, sessions that expire, and the hash-only path Ethereum is taking). In user experience it has no shape yet — and that is where our projects are, at bottom, an experiment.
A bunker assumes the key is only a safe. When the key also opens the door of your house, the long-term strategy is not to move out: it is to have two.
Step 5: accept reality

The reference survey is run by William Gasarch every seven years, and the result is stable: in 2002, 61 out of 100 respondents believed P ≠ NP. In 2012, 126 out of 152 (83%). In 2019, 109 out of 124 (88%). The dominant belief is strong, but notice it is not unanimity, and that among the few who bet on P = NP there are serious people.
More interesting than the percentage is why there is no proof. And here complexity theory has an unusually concrete answer: the barriers. There are three, and they are proven:
- Relativisation (Baker, Gill and Solovay, 1975): there are oracles that make P = NP and oracles that make P ≠ NP. Any technique that works the same with or without an oracle — diagonalisation, for instance — cannot settle the question.
- Natural proofs (Razborov and Rudich, 1997): the great method for proving impossibilities about circuits has a property which, if satisfied to the letter, would also break the cryptography we believe to be secure. Proving P ≠ NP with those tools would be proving something that implies the falsity of a belief nobody wants to give up.
- Algebrisation (Aaronson and Wigderson, 2009): the technique that overcomes the previous two is also blocked, by an algebraic version of the oracle argument.
Translated: it is not that nobody has found the proof. It is that the known techniques are formally ruled out, and each one was ruled out by a theorem. That is why P vs NP is different from other open problems: the difficulty is not a lack of attempts, it is that we know attempts of a certain kind will not work.
And there is a more uncomfortable fold: it is conceivable — not proven, conceivable — that P ≠ NP is independent of ZFC, that is, that neither the proposition nor its negation can be proven from the standard axioms of mathematics. In the 2012 survey, 3% chose that option. There are conditional results (Ben-David and Halevi, 1992) showing that, under certain cryptographic hardness assumptions, P ≠ NP would be unprovable in weak fragments of arithmetic. It is not a coffee-shop fantasy: it is a possibility serious people write down.
Does this mean the field is frozen? No. In 2025, Ryan Williams proved that every multitape Turing machine running in time t can be simulated in space O(√t · log t) — the first substantial improvement in 50 years over the result of Hopcroft, Paul and Valiant (1975). It is a result about the space around the wall: the relation between time and memory, the limits of computation in general. The million-dollar problem is still intact, and the theory is still moving.
Step 6: collect your million (or give up like everyone else)

Say you have the proof tomorrow. Do you get paid?
The Clay rules, revised in 2018, have three conditions: the proof must be published in a “Qualifying Outlet”, at least two years must have passed since publication, and the solution must have achieved general acceptance in the mathematical community. Only then does the committee decide whether it is worth analysing. Direct submissions are not accepted. The reason for the two years is not bureaucracy: it is accumulated experience.
And we have the perfect case study, from last year. In 2025, the journal Frontiers of Computer Science (Springer) published a paper titled “SAT Requires Exhaustive Search”, whose author is a Deputy Editor-in-Chief of that same journal, with a result stronger than P ≠ NP. The technical comment by Eric Allender and Ryan Williams showed that the main theorem’s lower bound contradicts a twenty-year-old algorithm by Williams, running in time O(d^(0.8n)) in the very case the paper declares impossible. They recommended retracting the paper. The editor-in-chief refused, saying he could find no evidence of misconduct; the comment ran with its closing paragraph cut. That is: a proof of P ≠ NP, published in an indexed journal, with one of the journal’s own editors as author, passed peer review and is still there. That is exactly what the two years and the “general acceptance” exist to filter out.
And machine-assisted proofs? In June 2026, a paper appeared on arXiv formalising in Lean 4 a theorem named p_equals_np: 36 files, nearly three thousand build targets, zero sorrys. The chain is: the membership problem for the pedigree polytope is polynomial, symmetric TSP reduces to that problem via the multistage insertion formulation, and therefore P = NP.
Here we have to be precise, because on this blog we already told how Lean secured the Ironwood circuit and we do not want to say two different things: Lean does not verify that the mathematics is the right mathematics: it verifies that the conclusion follows from the hypotheses you gave it. It is not an oracle of truth, it is the replacement of human error inside a chain of deductions. All the weight stays on the step that is not mechanised: that the multistage insertion formulation is a valid reduction from TSP, and that the definition of the polytope is the one the paper says it is. An impeccable theorem is only as strong as the modelling that feeds it — and arXiv, unlike a Qualifying Outlet, reviews nothing.
It is the same asymmetry of this article, turned inside out: verifying is easy, modelling is not.
The vault

The last panel leaves a better image than it seems: the Clay Institute’s million dollars is still intact, waiting inside a vault whose password is easy to verify but apparently impossible to solve. The vault is itself the theorem. It is the asymmetry made into an object.
And that asymmetry is what holds up everything we have been telling in this series. The zero-knowledge proof with which Zcash secures a pool is verified in milliseconds and produced in minutes: we use the gap on purpose, in our favour. PeerDAS does not download the block: it samples a few cells and knows. Ğ1’s web of trust does not ask for the whole truth: it asks for five signatures that expire and get renewed. In all three cases the same epistemic move is made — you do not need to have all of it to know that it is fine — and in all three cases someone is exploiting an asymmetry between producing and checking.
That is why P vs NP is not a riddle for mathematicians. It is the question about what kind of world we inhabit: one where believing is cheaper than knowing, and where that discount can be manufactured at will, or one where the shortcut of verification can be undone backwards and everything stored is left in plain sight.
We do not know which of the two is ours. We bet the financial system, communications, identities and the keys to your funds that it is the first one. So far the vault has held.
The million is still inside. And the question is still open, just as in the first panel: if verifying is cheap, why does solving have to be expensive?