Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror

Slashdot videos: Now with more Slashdot!

  • View

  • Discuss

  • Share

We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).

×

+ - John Nash's NSA Correspondance->

Submitted by Corporate T00l
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
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

John Nash's NSA Correspondance

Comments Filter:

Ya'll hear about the geometer who went to the beach to catch some rays and became a tangent ?

Working...