From U of T's Faculty of Arts & Science news page
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 appears arcane, it is the digital ghost that touches 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.”
A symposium exploring unknowable knowns
In May, many of the researchers who have spent their careers exploring this and related ideas attended a symposium in Toronto, organized by the Fields Institute for Research in Mathematical Sciences.
The event celebrated fifty years of computational complexity and the groundbreaking contribution to the field made by Cook, a professor in U of T’s Department of Computer Science.
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 — one of more than 30 former grad students of Cook’s — is a faculty colleague in the Department of Computer Science and one of the organizers of the symposium. She has said that the P versus NP problem is the driving force behind her work.
“Steve is a great mentor and role model, and has unbelievable intuition and taste in problems,” says Pitassi. “He introduced me to many important and fundamental concepts that have been important lenses through which I think about a lot of different problems.
“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, an invited speaker at the symposium. “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
The symposium celebrates Cook’s 50-year career, one which started not with computers but electrical engineering.
As a teenager, Cook was recruited by a family neighbour, the engineer and inventor Wilson Greatbatch, to help assemble circuitry for the implantable cardiac pacemakers he 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, until in 1970 he was enticed into becoming an associate professor at U of T, partly by the potential of the young computer science department, and partly by Lake Ontario where he could pursue the pastime he had grown to love in Berkeley: sailing.
Cook was named a University Professor, the University’s highest academic honour 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.”
About the symposium, Cook said prior to the event, “It’s extremely kind of people to do this. I’m overwhelmed that so many people are coming from all over the world to give talks — many of them former students of mine. I’m quite amazed.”
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 that comprises computational problems of many different stripes.
P problems can be solved by computers in a reasonable amount of time. Among them are multiplication or 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.
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 and can’t easily be solved in a reasonable amount of time.
Take the Travelling Salesman Problem (TSP). Suppose a travelling 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 deciding which is shortest. But double that 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.
Problems like TSP are NP-complete because the algorithm needed to solve them 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. 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!”