Quote: P=NP? Knuth said:

(1995)

P=NP is the most famous unsolved problem in computer science, analogous to Fermat's Last Theorem, although the P=NP problem has only been around for about 30 years, 25 maybe. In the context of combinatorial algorithms, it says: Are we going to be able to solve problems that would require going through 2^n cases? Can we actually do those in n^10, or something like that, if we knew the best method? if P=NP, the answer would be "yes", with some polynomial: we could reduce all these exponential problems to polynomial problems. If not, the answer is "no", we'll never to able to reduce them.

I have a feeling that someone might resolve the problem in the worst possible way, which is that following. Somebody will prove that P is equal to NP because there are only finitely many obstructions to it not being equal to NP. [laughter] The result would be that there is some polynomial such that we could solve all NP problems in polynomial time. However, we won't know what the polynomial is; we'll just know that it exists. So maybe the complexity will be n to the trillionth or something like that --- but it'll be a polynomial. In such a scenario we'll never be able to figure it out because it would probably take too long to find out what the polynomial is. But it might exist. Which means that the whole question P=NP was the wrong question![laughter] It might go that way. You see, even if you have a method that takes 2^n steps and you compare it to a method that takes n^100, then at least you can use the 2^n one for n up to 20 or 30. But the n^100 you can't even do for n=2. So the degree of that polynomial is very important. There are so many algorithms out there, the task of showing that no polynomial algorithms exist is going to be very hard. Still, I really thought that Fermat's Theorem was a similar kind of thing, where it was more important to have the problem than to solve it. Therefore, my real feeling about Wiles's Theorem is that he did a marvelous wonderful piece of work, but I wish he'd solved something else! [laughter]

A lot of people think that as soon as a problem is shown to be in this class NP, they shouldn't work on it, because it means that there's probably no polynomial way to solve the problem. But before we studied NP, we had unsolvable problems --- problems for which there didn't exist any algorithms at all. No matter how long you worked, you could never solve the problem. To tell whether a given Turing machine ever stops: This problem is unsolvable by any algorithm, in general, no matter how long you give yourself. In the days before NP became famous, people would stop working on a problem as soon as it was proved to be unsolvable in general. But that was a bad strategy, because almost every problem we ever solve is a special case of some unsolvable problem.

Take calculus, for example --- the problem of taking a formula, a function of n, and saying: "Is the limit as n goes to infinity equal to zero or not?" That's an unsolvable problem. But its unsolvability doesn't imply that we shouldn't study calculus. I mean, limits of lots of useful functions do go to zero, and therefore people were able to develop calculus. But the general problem is unsolvable. I mean, you could define f of n --- it only takes a few lines to make a formula that is equal to zero if a given Turing machine is stopped at time n, and it's equal to 1 if the Turing machine is still going at time n. And so the limit is equal to zero if and only if that Turing machine stops. It's unsolvable.

A similar thing happens with NP. That is, we have lots of special cases of problems that are NP-hard that we can solve efficiently; just knowing that something is NP doesn't mean that it's a good idea to give up on it or to stop trying to get good heuristic methods for it.