Related: * Kurt Gödel's Letter to John von Neumann (1956) https://news.ycombinator.com/item?id=19281633 https://news.ycombinator.com/item?id=19281633 Gödel w

Related: * Kurt Gödel's Letter to John von Neumann (1956) https://news.ycombinator.com/item?id=19281633 https://news.ycombinator.com/item?id=19281633 Gödel was asking John von Neumann the number of steps for solving the Entscheidungsproblem. I asked on HN for its background, and I was told it was one of the earliest discussions of computational complexity theory, unfortunately John von Neumann did not have a chance to reply. Thanks for posting it, now I see the bigger picture: even without seeing Gödel's letter, John von Neumann had already grasped the idea of computational complexity independently around the same time.