Gödel, von Neumann and the P =? NP Problem
Juris Hartmanis · WORLD SCIENTIFIC eBooks · 1993
In a 1956 letter, Godel asked von Neumann about the computational complexity of an NP complete problem. In this column, we review the historic setting of this period, discuss Godel's amazing letter and why von Neumann did not solve the P = ?NP problem.