Nash's beautiful mind pre-empted million-dollar puzzle
Source: Jacob Aron
John Nash's mind is even more exquisite than we thought. The Nobel laureate, famous for both his work in game theory and his schizophrenia �C as portrayed in the book and film A Beautiful Mind �C had ideas about cryptography and complexity decades before their time.
The revelations come in recently declassified handwritten letters exchanged between the US National Security Agency and Nash in 1955.
At a time when cryptography schemes were mostly advanced versions of the Enigma machine used by the Nazis in the second world war, Nash's letters detail an encryption technique based on the difficulty of computing certain mathematical functions �C an idea that underlies modern cryptography, but was not developed publicly until the mid-1970s.
"This is not a letter that you would have expected to have been written in the '50s," says Lance Fortnow, a complexity theorist at Northwestern University in Evanston, Illinois.
P versus NP
Nash also distinguishes between functions that run in polynomial time and those that run in exponential time. The former are roughly considered "easy" and belong to the set "P", while the latter are "hard" and in the set "non-P", according to modern theories of computational complexity. A third set, known as NP, involves functions for which it is hard to compute an answer but easy to check whether a proposed answer is valid.
A major unsolved problem is whether P is equal to NP �C most people suspect it isn't, but a proof either way is worth $1 million from the Clay Mathematics Institute in Cambridge, Massachusetts.
The "P versus NP" problem, which burst into headlines in 2010 thanks to a possible proof that was later shown to be wrong, was first posed publicly in 1971. Nash's letter appears to anticipate it by suggesting that encryption schemes based on exponential functions are essentially unbreakable.
"In today's language, his conjecture would imply that P is not equal to NP," says Aaron Roth, a computer scientist at the University of Pennsylvania in Philadelphia. "He even correctly anticipates that this will be hard to prove, and says that he does not expect it will ever be proven."
No circle-squarer
This isn't the first time a prediction about the P versus NP problem has come to light. In 1956 mathematician Kurt Gödel wrote a letter to computing pioneer John von Neumann laying out the problem much as it appeared in 1971. But von Neumann was suffering from cancer and died soon after, so the letter disappeared and did not resurface until the late 1980s. Nash's letter is not quite as explicit as Gödel's in proposing the problem, but predates it by a year.
It is hard to know what the NSA made of Nash's letter, which is full of crossed-out words and other scribbling. "I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer", he writes. A now-declassified response letter seems to dismiss his ideas: "It has been found that the cryptographic principles involved in your system, although ingenious, do not meet the necessary security requirements for official application," it says.
Was this a mistake, given Nash was essentially proposing modern cryptography 20 years in advance? "Back then they had different kinds of requirements; they were thinking about cryptography in a different way," says Fortnow. Adds Roth: "Perhaps they did use some ideas from his letter and did not tell him, or perhaps they already internally had similar ideas. Who knows?"
| }
|