●Stories
●Firehose
●All
●Popular
●Polls
●Software
●Thought Leadership
Submit
●
Login
●or
●
Sign up
●Topics:
●Devices
●Build
●Entertainment
●Technology
●Open Source
●Science
●YRO
●Follow us:
●RSS
●Facebook
●LinkedIn
●Twitter
●
Youtube
●
Mastodon
●Bluesky
Please create an account to participate in the Slashdot moderation system
Forgot your password?
Close
wnewsdaystalestupid
sightfulinterestingmaybe
cflamebaittrollredundantoverrated
vefunnyunderrated
podupeerror
×
29421213
journal
Journal
by
Corporate T00l
urday February 18, 2012 @12:36AM
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.
« Newer
Older »
Write in Journal
Slashdot Top Deals
●(email not shown publicly)
●
Member of the 10010 Digit (binary) UID Club
●
Days Read in a Row
●
Years Read
●
Wait... it's still up on eBay?
●
Correction: Isn't this a win for Roku?
(Score:2)
●
Isn't this a win for Google?
(Score:4, Insightful)
●
Voting Data Analysis
(Score:5, Informative)
●
Re:How unusual is this?
●
flamebait (comments)
●
informative (comments)
●
interesting (comments)
●
offtopic (comments)
●
troll (comments)
●
John Nash's NSA Correspondance
●
Google punishes itself via PageRank
Slashdot
●
Submit Story
It is much harder to find a job than to keep one.
●FAQ
●Story Archive
●Hall of Fame
●Advertising
●Terms
●Privacy Statement
●About
●Feedback
●Mobile View
●Blog
Do Not Sell or Share My Personal Information
Copyright © 2026 Slashdot Media. All Rights Reserved.
×
Close
Working...
Do Not Sell or Share My Personal Information
Copyright © 2026 Slashdot Media. All Rights Reserved.
×
Close
Working...