Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 internet speed test! ×
User Journal

Journal Journal: John Nash's NSA Correspondence

Aaron's "Adventures in Computation" blog has an interesting piece where he writes:

What this is, is a recently declassified correspondence between John Nash and the NSA from January 1955. In it, John Nash makes the distinction between polynomial time and exponential time, conjectures that there are problems that -cannot- be solved faster than in exponential time, and uses this conjecture as the basis on which the security of a cryptosystem (of his own design) relies. He also anticipates that proving complexity lower bounds is a difficult mathematical problem.

These letters predate even Godel's letter to Von Neumann, which goes into much less detail about complexity, and yet has also been taken to anticipate complexity theory and the P vs. NP problem.

Slashdot Top Deals

NOWPRINT. NOWPRINT. Clemclone, back to the shadows again. - The Firesign Theater

Working...