Devlin doesn't hide his feelings about the P versus NP problem as "the one most likely to be solved by an unknown amateur." He does make a point that if P = NP we can break RSA and "the current dependence of the Western economies on secure communications over the Internet demonstrates just how high are the P = NP stakes."
Let's play make believe and assume P = NP in a strong way, say that we can find satisfying assignments of Boolean formula in nearly linear time with small constants. It will have a dramatic influence on the Western economy but not at all in the way Devlin perceives. We'll lose public-key cryptography but what we will gain from it will make the whole internet look like a footnote in history.
Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.
Everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface.
P = NP would also have big implications in mathematics. One could find short fully logical proofs for theorems but these fully logical proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonably length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with one million-dollar check but with seven.
How would a strong P=NP generate proofs for theorems <100 pages? Wouldn't we still have to iterate through all of them and verify? From a given mathematical expression, how could strong P=NP be used to prove it?
ReplyDelete(Alas, if only we had such techniques now, we could get a resolution to the P=NP problem ;-)
Hi Lance,
ReplyDeletemost of these claims (if P = NP?) are, I think, not necessarily
valid because, even though there is a polynomial-time algo for
SAT, it may be of order n^1000 - how can we consider such an algorithm ``efficient'' or ``acceptable''? But, I guess we want
to show that SAT is intractable by showing that P \neq NP.
Russell Impagliazzo described a world where P=NP
ReplyDeleteby an efficient (e.g., linear-time) algorithm in http://www.cs.ucsd.edu/users/russell/average.ps
One consequence of this is that also the polynomial hierarchy collapses to P. This means that we should be able to solve questions like: "given this list of papers of Erdos, what is the smallest circuit that produced this list". Then, we could probably be able to predict the next paper on the list using this circuit. This of course works for books, paintings, movies, etc.. (Finding out the "blockbuster" formula for movies is certainly worth more than few millions)
--Boaz Barak
Hi Lance, On a second look I see that you already noted most of what I wrote in my comment --Boaz
ReplyDeleteLance, this was a fun post. I've been thinking about writing a science-fiction fantasy story wherein one person, for reasons unknown, performs subconsciously as a SAT oracle. It was intended to be an analysis of the sort you and Devlin give, crossed with a satire of the "Humans are better than computers because we are nondeterministic" argument you hear now and then.
ReplyDeleteHowever, I gave up because I couldn't get beyond really fuzzy ideas, and figured I needed to learn (still) more theory.
But I have a question - isn't finding the smallest program to fit some data exactly equal to finding the Kolmogorov complexity of that data? And this problem is Uncomputable, so P=NP wouldn't help at all (in the general case). Are you making extra assumptions about what the data are, or am I missing something else? Is mathematical-theorem-data actually less general than data?
(Also, are you aware that Blogger tells me that I cannot post anonymously and then permits me to do so?)
This comment has been removed by a blog administrator.
ReplyDeleteA seven million dollar award for showing "P \neq NP" is okay, and it makes sense that we would have an easier and more efficient life assuming P=NP. However, a person who happens to (constructively) prove P=NP is better to be somehow fined instead, for introducing a totally disappointing world where even creativity has lost its meaning by being automated!
ReplyDeleteHi Mahdi... perhaps then we would see a new brand of luddites if P=NP. I would rather like to live in Algorithmica, though. Technology can be used to liberate or to oppress... and *overall* it has so far lead us to liberation.
ReplyDeleteOne commentor correctly notes that finding the smallest program consistent with some data is not computable. I meant to say the smallest program with some reasonable (like quadratic) running time or even better the smallest circuit consistent with the data. These we can find if P = NP.
ReplyDeleteI'm curious...Devlin remarks that mathematics has reached the stage where the leading problems are incomprehensible to the experts, but cannot these same problems be recast into other problems that are more digestable ala Fermat?
ReplyDeleteRaphael
How can one check a proof of length $N$ in polynomial time in $N$? This is far from obvious to me, because each step of a proof can refer back to any of the prior conclusions of the proof, which makes checking rather complex.
ReplyDeleteI believe that this proof is simple, and easy to understand. If you don't understand computers, just read the comments at the bottom.
ReplyDeletehttp://www.mysqlperformanceblog.com/2011/05/17/using-sets-to-solve-difficult-decision-problems-the-subset-sum-problem/
Will quantum computers idea become irrelevant with strong P=NP? What about the new Bitcon-mania? Will this go total lost, its a market cost billions this days...
ReplyDeleteHello, I have the proof for P=NP in the folowing Scribd page: https://pt.scribd.com/doc/307232804/Solving-the-Traveling-Salesman-Problem-and-establishing-P-NP
ReplyDeleteSuppose the salesman was blind. He had to walk at a random angle to find the cities. The edges that decompose the space of n, to find each vertex, also form a graph of intersecting points, which in turn form undirected edges.
ReplyDeleteIt could be said that a solution that efficiently determines what angle the next edge is formed at to decompose the space, also forms a directed graph as a set of potential solutions.
Also 1 / e is a good number, check out the secretary problem sometime.
Even if P = NP, wouldn't most hard problems remain open due to their generalized versions not necessarily being in NP? Just because P = NP does not make generalized 3n+1 any more difficult.
ReplyDelete