Every month or so, an email appears in Stephen Cook’s inbox from someone claiming to have solved one of the most important questions in computational science. Should one of Cook’s correspondents actually solve the problem, they will–in addition to transforming an entire research field and having their name go down in scientific history–win $1 million from the Clay Mathematics Institute of Cambridge for having solved one of the Institute’s seven Millennium Prize Problems.
The question asks whether there is a type of problem that a computer program–or algorithm–fundamentally cannot solve. The idea is at the heart of a field of study known as computational complexity and has been represented for almost 50 years in a simple, Shakespearean form:
Does P = NP or does P ≠ NP ?
Or, as mathematicians and computer scientists put it: Are polynomial problems (P) like multiplication fundamentally the same as non-deterministic polynomial problems (NP) like calculating the optimal route for a delivery truck? Or, are NP problems fundamentally different and unsolvable?
The concept is also referred to as “P versus NP” or “P =? NP.” And while it may seem like counting angels on the head of a pin, it is the computational taxonomy that orders much of what we do with today’s computers and algorithms. University of Austin Texas computational scientist Scott Aaronson has spent much of his career exploring the problem and has written that “modern cryptography, quantum computing and parts of machine learning could all be seen as flowers that bloomed in the garden of P =? NP.”
Truths knowable and unknowable
In 1971, Cook defined a class of NP problems called NP-complete that appeared to be fundamentally unsolvable. He proposed that if just one of the many NP-complete problems is also in P, then they all are–meaning P = NP. But if just one of the NP-complete problems is not in P, then none are.
Toniann Pitassi is one of more than 30 former grad students of Cook’s and is now a faculty colleague in the Department of Computer Science at the University of Toronto. She has said that the P versus NP problem is the driving force behind her work.
“Computational complexity is the study of the inherent limitations of computation,” she says. “It is about proving barriers. The most important problem concerns how much computing time it takes to solve important and fundamental problems. The significance of this is hard to underestimate.”
“Cook’s contributions to computational complexity were absolutely foundational,” says Aaronson. “His discovery in 1971 is rightly credited with launching computational complexity as an autonomous field in the first place.
“It deals with some of the deepest questions that it’s possible to ask–questions about which types of necessary truths are or aren’t knowable by beings like us, who are constrained by the resources of the physical world.”
From soldering circuits to computational complexity
Cook’s 50-year career started, not with computers, but electrical engineering.
Image: Fundacion BBVA
As a teenager, he was recruited by a family neighbour, the engineer and inventor Wilson Greatbatch, to help assemble circuitry for the implantable cardiac pacemakers the medical researcher was pioneering. With that early exposure, Cook enrolled in the electrical engineering program at the University of Michigan. But, very soon he was studying computer programming and taking advanced math courses and by his third year had switched to the mathematics program. As a graduate student in the mathematics department at Harvard, he was exposed to early work in computational complexity and received his PhD in 1966 with a thesis on the complexity of multiplication.
Cook spent the next four years at the University of California, Berkeley, but famously was not offered another appointment. (According to Berkeley’s Richard Karp, “It is to our everlasting shame that we were unable to persuade the math department to give him tenure.”) However, he was enticed to become an associate professor at U of T by the potential of the nascent computer science department and by Lake Ontario where he could pursue the pastime he had grown to love in Berkeley: sailing.
Cook was named a University Professor, the U of T’s highest academic distinction in 1985 and has received numerous honours for his work. He is an Officer of the Order of Canada, a Fellow of the Royal Society of London and the Royal Society of Canada; a member of the National Academy of Sciences (US) and the Gottingen Academy of Sciences, and a Fellow of the American Academy of Arts and Science. In 1982, he received the A.M. Turing Award, the “Nobel Prize of computer science.”
Does P = NP or does P ≠ NP? That is the question.
P versus NP and Cook’s NP-complete question arise from the collection of computational problems referred to as the “complexity zoo”: a menagerie comprising computational problems of many different stripes.
P problems can be solved by computers in a reasonable amount of time. Among them are multiplication and sorting a list of numbers, calculations which can be completed in a fraction of a second, even for very big numbers or very long lists. (Try it. How quickly can your phone’s calculator multiply two enormous numbers like 457,378,991,003 and 775,099,184,818?)
NP problems are more difficult to solve but you can at least easily check whether a given solution is correct. For example, it’s relatively easy to check if a solution to a Sudoku puzzle is correct by making sure each row, column and square contains the numbers one to nine–with no repeated or missing numbers.
However, NP-complete problems seem to be fundamentally different. An NP-complete problem can’t easily be solved in a reasonable amount of time; nor can a solution be easily checked.
Take the Travelling Salesman Problem (TSP). Suppose an itinerant salesman has a number of cities to visit and wants to travel the shortest distance before returning home. If there are only a few cities, the problem isn’t difficult; a relatively simple algorithm can plot the shortest route in a reasonable amount of time.
But with every additional city, plotting the shortest route quickly becomes intractable. For five cities, an algorithm wouldn’t have too much trouble determining the 120 possible routes and calculating which is shortest. But double the stops to 10 cities, and the number of possible routes doesn’t merely double; it grows exponentially to more than three million. And for 50 cities, there are so many routes to evaluate, a computer would need the age of the universe to identify them and determine which is shortest.
To understand the pace of exponential growth, consider the fable of the inventor who offered his latest creation–the game of chess–to his king. In return, the inventor asked the king for a modest reward: rice. But, he stipulated, it was to be paid in this manner: place one grain of rice on the first square of the chessboard; two on the second; four on the third; eight on the fourth; and so on. In the fable, the king agreed to the seemingly meager payment but soon discovered there wasn’t enough rice in his kingdom to fulfill the payment as filling 64 squares required a total of 18,446,744,073,709,551,615 grains.
Problems like TSP are NP-complete because the algorithm needed to solve them and the computer needed to run the algorithm would simply require an unrealistic amount of time to run.
Who wants to be a millionaire?
As Cook first proposed, if a single NP-complete problem is solvable then they all are and P = NP. Such a discovery would be the computational complexity equivalent of the discovery that stars in the night sky are suns not unlike our own. Seemingly unsolvable NP problems would in fact be solvable P problems and the solution to any would lead to solutions for all of them.
“There are an astounding number of problems,” says Pitassi, “that are in a sense equivalent to the traveling salesman problem, so if we could find an efficient solution to any one of them, we would immediately have efficient solutions to all of them. This is one of Cook’s breakthrough results that earned him the Turing award.”
And the resolution wouldn’t just open up a new realm of solutions to problems in industry and technology; in Cook’s words, “mathematics would be transformed.”
But if P ≠ NP, then the two types of problems are and will forever be distinct, and NP problems would remain unsolvable – at least with today’s computers and algorithms.
“Much of modern cryptography,” says Pitassi, “relies on the difficulty of computing these and other problems. So, from this point of view, a proof that P is not equal to NP would be a major step in proving the security of the internet.”
Think you know the answer to P versus NP and can prove it? Then the Clay Mathematics Institute has a cheque for you for $1 million dollars. Just don’t email Cook to verify the answer.
“There are many thousands of people who think they’ve solved it,” he says with a smile. “They email and say, ‘Please look at this! I think I’ve solved P versus NP!’ But, I’m sorry, I’m just too busy!”
I originally wrote this for the University of Toronto’s Faculty of Arts & Science website. It has been edited for World of Wonders. You can read the original article here.
Filed under: computer science, U of T Faculty of Arts & Science
World of Wonders 