John Nash Wrote the NSA About P vs NP in 1955

On January 18, 1955, the mathematician John Nash mailed a handwritten letter to the National Security Agency. He was 26, four years before the schizophrenia onset that A Beautiful Mind would later dramatize, and he wanted to talk about codes. The letter, declassified in 2012, proposed a cipher and made a more interesting claim about cryptography in general: the time to break a sufficiently complex cipher should grow exponentially in the key length. Nash wrote that he couldn't prove it, but he believed it and thought the NSA should care.

What Nash was groping toward, in 1955, was the question that Stephen Cook would formalize sixteen years later as P vs NP.

The problem, in modern form. P is the class of decision problems solvable by a deterministic Turing machine in polynomial time — time bounded by some fixed power of the input size. NP is the class for which a proposed solution can be verified in polynomial time. Sudoku is the cliché example. Filling in a 9×9 grid is hard; checking that a filled grid satisfies the rules is trivial. The question is whether "can be checked fast" implies "can be solved fast." Equivalently, whether P = NP.

Cook gave the question its current shape in a paper presented at the Stouffer's Somerset Inn in Shaker Heights, Ohio, on May 4, 1971, at the third ACM Symposium on Theory of Computing. The paper, "The complexity of theorem-proving procedures," introduced the concept of NP-completeness and proved that the Boolean satisfiability problem (SAT) is NP-complete: every problem in NP reduces to SAT in polynomial time. If you could solve SAT fast, you could solve all of NP fast. If you couldn't, you couldn't.

Leonid Levin, working in the Soviet Union with no contact with Cook, proved an essentially equivalent theorem and published it in 1973. The result is now standard called the Cook–Levin theorem. Within a year of Cook's paper, Richard Karp showed that 21 well-known problems — graph coloring, the traveling salesman, knapsack, vertex cover, independent set — are all NP-complete. Today the list runs to thousands. They all stand or fall together.

What would it actually mean if P = NP? Most existing public-key cryptography would collapse: factoring, discrete logarithm, lattice problems are all in NP, so a polynomial algorithm for any NP-complete problem would, with effort, give polynomial algorithms for all of them. Optimization problems that today require heuristics — protein folding, circuit verification, scheduling — would have efficient exact solutions. Mathematical theorem-proving, in some bounded sense, would too: checking a proof is in P, so finding short proofs would be in P, and a great deal of mathematics would become a search problem. Scott Aaronson has put it that a P = NP world would be one in which Mozart-level music could be composed by anyone with a laptop, given a way to recognize Mozart-level music when you heard it.

The other direction is the one almost everyone bets on. A 2012 poll of complexity theorists by William Gasarch found 83% believed P ≠ NP. The intuition is that the gap between checking and finding really is exponential in general, and that the structure of NP-complete problems — their hardness amplifies under reductions — means a fast algorithm for any one of them is unlikely. None of this is proof.

The Clay Mathematics Institute put P vs NP on its list of seven Millennium Prize Problems in 2000, with a million-dollar bounty for a resolution either way. As of 2026, the bounty stands. Many proofs of P ≠ NP have been submitted; none have survived peer review. Many proofs of P = NP have been submitted; same fate. The standard professional response to a new such proof is to wait three months for the gap to be found.

What is striking about Nash's letter, read with sixty years of hindsight, is how cleanly he saw the shape of the question without the language to name it. He wrote that the gap between an enciphering process — easy — and the cryptanalytic effort needed to undo it — hard — was the kind of asymmetry that a serious cryptographic system would need. That asymmetry, in 2026, still has no proof. The whole field is, in a sense, a long appendix to a sentence Nash slipped into a letter that the NSA's cryptanalysts filed and forgot.