P versus NP problem

The P versus NP problem is a major unsolved problem in computer science and one of the seven Millennium Prize Problems.

Quotes

• 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. 

• Nowadays, mathematicians routinely use computers to solve problems, even great problems. Computers are good at arithmetic, but mathematics goes far beyond mere ‘sums’, so putting a problem on a computer is seldom straightforward. Often the hardest part of the work is to convert the problem into one that a computer calculation can solve, and even then the computer may struggle. Many of the great problems that have been solved recently involve little or no work with a computer. Fermat’s last theorem and the Poincaré conjecture are examples. When computers have been used to solve great problems, like the four colour theorem or the Kepler conjecture, the computer effectively plays the role of servant. But sometimes the roles are reversed, with mathematics as the servant of computer science. Most of the early work on computer design made good use of mathematical insights, for example the connection between Boolean algebra – an algebraic formulation of logic – and switching circuits, developed in particular by the engineer Claude Shannon, the inventor of information theory. Today, both practical and theoretical aspects of computers rely on the extensive use of mathematics, from many different areas. One of the Clay millennium problems lies in the borderland of mathematics and computer science. It can be viewed both ways: computer science as a servant of mathematics, and mathematics as a servant of computer science. What it requires, and is helping to bring about, is more balanced: a partnership. The problem is about computer algorithms, the mathematical skeletons from which computer programs are made. The crucial concept here is how efficient the algorithm is: how many computational steps it takes to get an answer for a given amount of input data. In practical terms, this tells us how long the computer will take to solve a problem of given size.
  • Ian Stewart. Visions of Infinity: The Great Mathematical Problems. Basic Books. p. 203. ISBN 978-0-465-06599-8.