P versus NP problem
unsolved problem in computer science about time complexity
The P versus NP problem is a major unsolved problem in computer science, asking whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
 |
This science article is a stub. You can help out with Wikiquote by expanding it! |
Quotes
edit- If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.
- Scott Aaronson. Reasons to believe., point 9.
- The P versus NP problem was first mentioned in a 1956 letter from Kurt Gödel to John von Neumann, two of the greatest mathematical minds of the twentieth century.
- Lance Fortnow (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press. p. 6. ISBN 0-691-15649-2.
- Every year the Association for Computing Machinery awards the ACM Turing Award, the computer science equivalent of the Nobel Prize, named for Alan Turing, who gave computer science its foundations in the 1930s. In 1982 the ACM presented the Turing Award to Stephen Cook for his work formulating the P versus NP problem. But one Turing Award for the P versus NP problem is not enough, and in 1985 Richard Karp received the award for his work on algorithms, most notably for the twenty-one NP-complete problems.
- Lance Fortnow (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press. p. 57. ISBN 0-691-15649-2.
