16 plus ones
Shared publicly•View activity
- The connections between computational efficiency and cryptanalysis were already becoming apparent in the time of Babbage, but that predates any hypotheses on lower bounds as far as I can tell. It's unfortunate that Nash's early formulation is for a key recovery attack, which overlooks the possibility of recovering plaintext without recovering the key. It's probably most interesting in his suggestion of an exponential lower bound - are there any other hypotheses about exponential separation between the time of Turing and 1955?
I really like the way he crossed out
informationand wrote instructions instead. Shannon's paper was declassified in 1949, so maybe he wanted to distinguish the information-theoretic approach from the complexity-theoretic approach.Feb 17, 2012