An interview with Lance Fortnow, author of The Golden Ticket: P, NP, and the Search for the Impossible
Why did you write this book?
I wrote a survey article on the P/NP problem for a computing trade magazine, Communications of the ACM http://bit.ly/pvnp-cacm, that quickly became the most downloaded article in that magazine's history. Clearly there was great interest in the P/NP question and there is no popular science book focused on P/NP or many on any computer science topic at all, so I took the survey I wrote as a template and started writing.
Ok, let's start with the basics, what is P/NP?
The P/NP problem is best described by an example question: Are there 1000 people on Facebook whom are all friends with each other? Even if you worked for Facebook and had access to all its data, answering this question naively would require checking more possibilities than any computer, now or in the future, could possibly do. The P/NP question asks whether there is some very clever algorithm that can answer this problem and others like it.
What is the history of this problem? When was it first formulated and by who?
The development of the P/NP problem has two histories, in North America and in Russia with researchers separated by the Cold War in the early 70's. In North America the problem developed in a rather conventional way, first defined by Steve Cook, a young professor, at the University of Toronto in 1971 as he looked at ways to connect logic and computation. A year later, Richard Karp of the University of California at Berkeley made the P/NP problem famous by tying it into a number of well-studied combinatorial problems. In Russia, progress was slowed by strong politics in their mathematical community, but eventually a young student, Leonid Levin, discovered the P/NP problem by looking at the difficulty of computer search. I devote a chapter of the book to the history and personalities leading up to the development of the P/NP problem on both sides of the Iron Curtain.
It matters because if P=NP it would make a large number of difficult computational tasks immediately easy to solve and it would transform our lives beyond measure: we'd cure major diseases, make accurate predictions of weather, get near prefect translation, and much more. The computer could find solutions to virtually any question we could ask of it.
It really sounds like the "golden ticket" of your book's title. But in the book, you also talk about some of the less positive outcomes to solving this problem. Can you describe those too?
We'd have a near complete loss of privacy as P=NP would allow anyone to reverse engineer any attempts to hide your activities. Also if P=NP virtually any job could be automated potentially leading to large-scale unemployment.
What makes it so difficult to solve?
If P is not NP as most computer scientists believe, to show this requires that there is no algorithm out of an infinite number of possible clever algorithms, to solve a problem like the Facebook question above. It's very difficult, though hopefully not impossible, to show that no algorithm exists.
So, scientists are also trying to disprove P/NP? Why is that also important and do you think this is more likely than solving P=NP?
Either P=NP or not, there exists one algorithm that solves most of the computational problems we care about or no such algorithm. Understanding which is the case will help us understand the best modes of attack on difficult computational problems. Because we don't expect the world to be so clean, with one algorithm that solves everything, the common belief of computer scientists is that P and NP are not equal.
Have there been any near solutions--people who thought they had a solution, but ultimately didn't? etc.
The P/NP problem has a $1,000,000 bounty for a solution offered by the Clay Mathematics Institute, so many people discover "solutions" they believe are correct but are usually flawed at a fundamental level. In 2010, HP researcher Vinay Deolalikar sent around a transcript that caused some initial hopes, but after an extensive discussion, was also found to have fundamental flaws. That experience was recounted by an article in the New York Times http://nyti.ms/XXeWAk)
What would solving P/NP mean for the world?
Showing P=NP would greatly transform the world as I mentioned before. Showing P and NP are not the same would be an amazing mathematical result but wouldn't have quite the dramatic effect on society. The power of the P/NP question doesn't really come from whether or not we find a solution. Rather P/NP tells us what's possible. Even if P and NP are different, the problems we can imagine solving if P=NP are often still solvable, it will just cause us considerably more effort instead of a single magic bullet.
What are the most promising areas of research on P/NP right now?
Very few. There is an interesting approach using an area of mathematics called algebraic geometry spearheaded by Ketan Mulmuley of the University of Chicago http://gct.cs.uchicago.edu But several people doubt this approach will work and even Mulmuley believes his program could settle P/NP, it would likely take well over a century.
What do you hope people take away from your book?
I hope people come to understand the importance of the P/NP problem and more generally come to realize that computer science is about tackling major computational challenges and not just about programming a computer.