Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

John Nash's NSA Correspondance

Corporate T00l (244210) writes | more than 2 years ago

0

Corporate T00l (244210) writes "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.

"
Link to Original Source

Sorry! There are no comments related to the filter you selected.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?