The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955. In this hand-written letter, he shows an amazingly prescient analysis anticipating computational complexity theory as well as …modern cryptography.  In the letter, Nash takes a step beyond Shannon’s information-theoretic formalization of cryptography (without mentioning it) and proposes that security of encryption be based on computational hardness — this is exactly the transformation to modern cryptography made two decades later by the rest of the world (at least publicly…).  He then goes on to explicitly focus on the distinction between polynomial time and exponential time computation, a crucial distinction which is the basis of computational complexity theory, but made only about a decade later by the rest of the world.

There is a well-known excuse with P ≠ NP among computer scientests: “I cannot prove this but neither can all.” This letter is the very first letter in which the mention is written (which is exposed just now!); this is even earlier than the famous Gödel’s Letter.