Godel, von Neumann and the P=?NP Problem

Hartmanis, Juris

Godel, von Neumann and the P=?NP Problem

File(s)

89-994.pdf (609.66 KB)

89-994.ps (175.35 KB)

Permanent Link(s)

https://hdl.handle.net/1813/6910

Collections

Computer Science Technical Reports

Hartmanis, Juris

Author

Hartmanis, Juris

Abstract

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.

Date Issued

1989-04

Publisher

Cornell University

Keywords

computer science

•

technical report

Previously Published as

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-994

Type

technical report