Godel's letter to Von Neumann: Computational Complexity years before its time

It's very interesting to see how Godel anticipates the major questions and goals in computational complexity, before the standard complexity paradigm was set.

It's also interesting to see how varied his interests were. I always feel very capricious when I mention a set of different concerns, ideas, or results in a letter to someone (indeed, I've been told to keep emails shorter), but I guess I'm in good company.