Is it easier to check if a problem’s solution is true than to find one yourself?
It turns out this question does not have a trivial answer, and this summer, Vinay Deolalikar, a mathematician at HP Labs, had the theoretical computer science community buzzing with a claim that he had solved the field’s biggest question: P vs. NP.
By “easy” computer scientists mean that the time it takes to solve a problem is bounded above by a polynomial in the size of the problem itself. Thus, this question, the so-called P vs. NP problem, asks whether every problem for which solutions can be verified in polynomial time can also be solved in polynomial time. If this were true, then P would equal NP.
The P vs. NP problem is still one of the deepest unsolved problems in mathematics and computer science. It was first described in 1971 by U of T’s own Professor Stephen Cook. While the consensus is now that Deolalikar’s proof has irreparable flaws, The Varsity took this chance to sit down with Professor Cook and discuss the famous problem.
The Varsity: How would you describe the problem to someone without formal training?
Stephen Cook: Well it’s a fundamental question in computer science and, [it] turns out, [in] all mathematics. The problem is whether search problems can be, in general, feasibly solved by deterministic algorithms. In other words, in the case when search problems have an exponential number of possible solutions, can you do better than going through all the possibilities?
It turns out that there are hundreds or even thousands of practical problems of this form that would be useful to be able to solve. Scheduling problems is one class of examples.
Think of a trucking company that has hundreds of destinations and a large fleet of trucks. They have to find optimal schedules. The number of possible schedules is so large for these cases that no computer could conceivably try all the possibilities without the sun burning out. So, that’s really the P vs. NP problem: can you find the optimal solution in polynomial time?
TV: You said that Deolalikar’s claim was “relatively serious.” What stood out to you about this proposal at the time?
SC: Two things. The first was that this is a respectable mathematician. He has a publication record in sound mathematical journals with respected co-authors. The second is that he announced it so positively. He said, “I’m pleased to present you with my proof that P is not equal to NP.”
TV: Why is it such a difficult problem?
SC: On the face of it, it’s a negative, and how do you prove something doesn’t exist? If you’re trying to prove P equals NP, then you just provide a polynomial time algorithm to solve any of the NP-complete problems. I mean, it’s tempting. So, laymen out there often think they’ve found polynomial time solution to one of these problems. It’s not so easy to see how to show there is no such algorithm. Not at all clear how to proceed.
TV: Thinking back to 1971, when you first described the problem, did you have a hunch about the solution? Was it coming down the pipeline or was it never going to come?
SC: Well I certainly conjectured that P is not equal to NP. As far as when it was going to be solved, I don’t think I had a clear idea. I spent some time early on thinking about it, and I didn’t get very far. So, I just treated it as an open problem.
TV: How have your intuitions about a possible solution changed in the past 40 years?
SC: I’ve become more convinced that it’s really hard and probably not going to be solved soon. Yet, it will be solved eventually. Think about the example of Fermat’s last theorem. It was open for 400 years, but finally solved. That was an interesting case, because a large amount of very sophisticated mathematical machinery had to be built in order to solve the problem. I would say we don’t have that machinery yet for P vs. NP.
TV: Vinay Deolalikar’s proof employed statistical mechanics; do you think statistical mechanics might be part of this machinery?
SC: There are computer scientists that are interested in the statistical mechanics point of view. My sense is that they don’t see much hope. There may be some optimistic ones, but it doesn’t seem very promising. Still, it is a very interesting approach.
TV: On a more personal note, how did your interest in computer science begin?
SC: I got interested in first year at the University of Michigan in 1957. Michigan was ahead of the game because they actually had computer science courses — not all universities did. Later I had summer jobs involving computers. When I went to graduate school in mathematics at Harvard, computer science wasn’t really a subject, but I found my future advisor, who was a logician with an interest in computation.
TV: Do you have any heroes?
SC: Alan Turing, the father of computer science. He introduced the model of computers before computers even existed, and Turing did prove things impossible. I said it’s very hard not to give non-existence proofs of algorithms, but he gave two: the predicate calculus decidability problem and the famous halting problem.
The Millenium Prize Problems
The P vs. NP problem is one of seven Millennium Prize Problems named by the Clay Mathematics Institute in 2000, each of which hold a one million dollar prize for a correct solution. To date, only one of these problems — the Poincaré conjecture — has been solved. The prize was conceived to show the general public that the field of mathematics still faces a number of deep unsolved problems. It was also meant to bring attention to the most difficult problems mathematicians are tackling in the new millennium. Although these are considered some of the world’s most important mathematical problems, not all of them hold foreseeable applications, constraining them to the domain of pure mathematics.
The Poincaré Conjecture
The Poincaré conjecture considers the topological properties that characterize a sphere. Grigori Perelman, the Russian mathematician to solve the famous problem in 2002, declined the Millenium Prize, as well as the Fields Medal — the mathematics community’s version of the Nobel Prize. He is also rumoured to still live with his mother.
The Riemann hypothesis
Considered by some mathematicians as the most important unsolved problem in pure mathematics, the Riemann hypothesis makes conjectures about the distribution of prime numbers. Although it has withstood many efforts at solution, Pierre Deligne proved the generalized version of the hypothesis, that it holds true over finite fields.
The yang-mills theory
The Yang-Mills theory is the quantum field theory underlying the Standard Model of particle physics. Although the mathematical foundation of quantum Yang-Mills theory remains unclear, its predictions have been tested experimentally, while the theory itself forms the foundation of much of elementary particle theory.
