Some consider the P = NP problem to be the most important Theoretical Computer Science problem. It asks whether all problems whose solution can be verified quickly, can also be solved quickly. If you can answer this question, you win one million dollars.
The catch is that quickly is defined as in polynomial time. Thus, if you can solve a problem in time O(nx) where x is the number of electrons in the universe, then you are quick.
This is an annoyingly silly definition. Bubble sort is in O(n2). Yet, try replacing all sorting within Google’s infrastructure by this quick algorithm. Google would die.
Lance Fortnow asks us to take for granted that proving P = NP implies we have fast algorithms for all NP problems. William Gasarch just predicted that proving P ≠NP would also help real world of algorithms.
Unknowingly to them, Zeilberger proved that P=NP on April 1, 2009. Yet, nothing happened. (He was kidding. Or was he?) Anyhow, enough with the dogma! While intermediate steps in the solution of the problem might be critically important to our understanding of computation, knowing that P = NP is inconsequential technologically.
This is as silly as claiming that sending men to Mars will cure cancer. It might very well that the research necessary to send men to Mars might lead to major breakthroughs, but whether we go to Mars or not has nothing to do with cancer.
Yes, please send men on Mars. Yes, please work on the P = NP problem. But stop claiming the answer would change the world.
Further reading: See my older post Is P vs. NP a practical problem?. Dick Lipton wrote a related blog post as well.
@Rasmus Yes, but how many of them were published on April 1st?
> Unknowingly to them, Zeilberger proved that P=NP on April 1, 2009. Yet, nothing happened.
Zeilberger’s was not the first person to “prove” it which might explain the lack of effect. The P=NP equality has been both “proven” and “disproven” numerous times before. Check out the “P-versus-NP Page” that provides a long list of contributions to the question:
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
As the page states:
Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but “just” shows that a certain approach to settling this question will never work out.)
More researchers should publish their results on April 1st as it would add a whole new dimension to science: “do the authors really mean it or is this paper just an Aprils fool?”. We could even have conferences dedicated to doubtful and/or silly results. 🙂
I think that you are taking the “P=NP” question too literally. Most people working on P=NP realize that the real question is simply to be able to understand the inherent complexity *limitations* of algorithms. I.e. we would like to be generally able to prove, for computational problems of interest, lower bounds that match (as closely as needed) the algorithms we have for them. The basic “P=NP” question is merely the *first approximation* of this goal. It is clear that after the first approximation, finer results will be needed for some applications, but this hardly reduces the importance of the first approximation. It is *theoretically* possible that once we get a resolution to the basic P=NP question, its form will be too coarse for much practical applications, but this would seem unlikely: historically, clean theoretical first approximations did turn out to be pretty enlightening practically too.
historically, clean theoretical first approximations did turn out to be pretty enlightening practically too
It’s possible that history is misleading here. To a first approximation, clean theory and practical results are relatively close, so the early results are in good agreement. However, the more we master the theoretical machinery and develop arcane techniques, the further theory gets from practice.
A good example is the foundations of cryptography. In polynomial time, we know how to build a pseudorandom generator from an arbitrary one-way function, or do secure multiparty computation, but the techniques are grotesquely impractical. These are fantastic results, and I don’t mean to criticize them. It’s very important to understand what can be done in simple models. However, in theoretical cryptography, the fact that we can do something in polynomial time seems to say very little about whether we can implement it in practice. In a sense, theorists have really figured out how to exploit the aspects of polynomial time that don’t perfectly match computing practice. Crypto seems to be a relatively extreme case, but I think this gradually happens over time in every area of theoretical CS.
Now the question about P vs. NP is how it would fit into this. One argument is that it would involve a dramatically new idea, and that the very newness would reset the clock on the drift between theory and practice. Another argument is that it would involve the ultimate mastery of technique, pushing our understanding of P and NP to the limit, and this process will naturally accentuate the differences between theory and practice.
I prefer the latter argument. If we ever prove P != NP, I bet it will show that 3-SAT requires time at least n^(log log log log log n) for n >= 2^(2^(2^(2^2))), and getting better bounds will be vastly more difficult than proving P != NP was.
This is as silly as claiming that sending men to Mars will cure cancer.
It’s not nearly that silly. It’s more like claiming that fully understanding the biological basis of cancer will let us cure it. It’s highly optimistic: we might understand cancer completely yet be powerless against it. However, it’s a necessary first step.
Depends…
Is putting a lot of mathematicians out of work inconsequential?
Is putting a lot of mathematicians out of work inconsequential?
Well, there’s a big difference between putting actual mathematicians out of work in the real world (which is one of the less plausible consequences of P=NP) and putting imaginary mathematicians out of work in a toy model of the world (which is a clear consequence of P=NP).
From a practical point of view, surely the value of proving that P=NP is that you would know that (a) there is a polynomial time algorithm to be found and (b) if you found it, you could, in principle, parallelize it and run it “efficiently” over a finite number of processors.
The point about discovering NOT(P=NP) is that you would know (b) not to be possible.
Knowing you *could* do (b) would get me worried about doing my on-line banking with a cryptographic key-exchange algorithm that uses prime-number factorization as its foundation.
if you found it, you could, in principle, parallelize it and run it “efficiently†over a finite number of processors
No, there’s no implication of parallelizability, and it’s very likely false. One related question is whether P=NC. NC is not a great model of parallelizability, but it’s theoretically elegant, and it is widely suspected that P != NC.
theorists have really figured out how to exploit the aspects of polynomial time that don’t perfectly match computing practice.
That sentence hits the nail on the head. Well said, Anonymous!
I just learned about P = NP first time.
Seems like it’s asking:
If you can tell food is good, can you cook it the same?