Around 1989, a striking letter written in March 1956
from Kurt Gödel to John von Neumann came to light.
It poses some problems about the complexity of algorithms; in particular,
it asks a question that can be seen as the first formulation of the
P=?NP question.
This paper discusses some of the background to this letter, including
von Neumann's own ideas on complexity theory.
Von Neumann had already raised explicit questions about the complexity of
Tarski's decision procedure for elementary algebra and geometry in a letter
of 1949 to J. C. C. McKinsey.
The paper concludes with a discussion of why theoretical computer science did
not emerge as a separate discipline until the 1960s.