The Golden Ticket by Fortnow Lance
Author:Fortnow, Lance [Fortnow, Lance]
Language: eng
Format: epub
Publisher: Princeton University Press
Published: 2013-03-26T21:00:00+00:00
The Gödel Letter
In 1956 Kurt Gödel wrote a letter to John von Neumann, one of the pioneers of computer science and many other fields. In this letter (written in German), Gödel talks about the satisfiability problem and formulates the P versus NP question in different terminology. He suggests that if we lived in a world where P = NP, “the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. … Now it seems to me, however, to be completely within the realm of possibility.” This letter predates the papers of Cook and Levin by fifteen years.
We do not know if von Neumann responded or even saw this letter. Von Neumann had cancer at the time of the letter and passed away in 1957. The letter itself was unknown to the general scientific community until the late 1980s, well after the P versus NP problem was firmly established as a major open question. Gödel passed away in 1978 but was not in the right mental state in those last years of his life to notice that Cook had restated his question.
Since Gödel discovered the P versus NP problem years before Cook and Levin, why don’t we call whether P = NP “Gödel’s problem,” and give him the credit? Science, for better or for worse, uses the Columbus principle: Christopher Columbus is famous not for being the first person to discover America but for being the last person to discover America. Gödel himself was not blameless. He didn’t realize the importance of the question he raised with von Neumann and never mentioned it in a public venue. Cook and Levin still have the first published papers that state the P versus NP problem.
In honor of Gödel’s fundamental work in logic and the Gödel letter, the theoretical computer science community initiated the Gödel Prize in 1993 to recognize recent outstanding research papers in the field.
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Biomathematics | Differential Equations |
Game Theory | Graph Theory |
Linear Programming | Probability & Statistics |
Statistics | Stochastic Modeling |
Vector Analysis |
Weapons of Math Destruction by Cathy O'Neil(5015)
Factfulness: Ten Reasons We're Wrong About the World – and Why Things Are Better Than You Think by Hans Rosling(3996)
Factfulness_Ten Reasons We're Wrong About the World_and Why Things Are Better Than You Think by Hans Rosling(2745)
Descartes' Error by Antonio Damasio(2718)
A Mind For Numbers: How to Excel at Math and Science (Even If You Flunked Algebra) by Barbara Oakley(2675)
TCP IP by Todd Lammle(2615)
Applied Predictive Modeling by Max Kuhn & Kjell Johnson(2460)
Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets by Nassim Nicholas Taleb(2399)
The Book of Numbers by Peter Bentley(2392)
The Tyranny of Metrics by Jerry Z. Muller(2387)
The Great Unknown by Marcus du Sautoy(2170)
Once Upon an Algorithm by Martin Erwig(2136)
Easy Algebra Step-by-Step by Sandra Luna McCune(2104)
Practical Guide To Principal Component Methods in R (Multivariate Analysis Book 2) by Alboukadel Kassambara(2082)
Lady Luck by Kristen Ashley(2059)
Police Exams Prep 2018-2019 by Kaplan Test Prep(2018)
Linear Time-Invariant Systems, Behaviors and Modules by Ulrich Oberst & Martin Scheicher & Ingrid Scheicher(1977)
All Things Reconsidered by Bill Thompson III(1951)
Secrets of Creation, Volume 1: The Mystery of the Prime Numbers by Watkins Matthew(1853)