How to Solve P=NP?
An approach to the solution of P=NP?
Landon Clay is the Boston businessman who help fund the Clay Institute and its seven associated Millennium Problems, one of which is P=NP. The person(s) who solves P=NP will get, after certain rules are fulfilled, a cool one million dollars. That is a lot of money, but somehow juxtaposed next to current bank bailouts and other loans measured in the trillions of dollars, it does seem a bit less impressive. But, unlike Grigori Perelman, I would take the money, for sure.
Today I want to talk about how I would approach the P=NP, if I was forced to work on it. I think of the quote from Paul Erdös on Ramsey numbers:
He asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for . In that case, he believes, we should attempt to destroy the aliens.
See our friends at Wikipedia for this quote and the definition of the Ramsey function .
My version is suppose that the alien force asks us to prove that P=NP. I would say get our best theorists and mathematicians and look for an algorithm. If on the other hand, they ask for a proof that PNP, I would agree with Erdös and suggest we attempt to destroy them.
You know why I believe this. Even if the conventional wisdom is that P=NP is false, I think we have a better chance of finding an algorithm, then a lower bound proof. I guess also if the aliens are “fair”, by asking for a proof that P=NP, one could conclude that it was true. To ask for a proof otherwise would make the aliens pretty mean. If they were that evil, they might just destroy us whether we solved P=NP or not.
There is a history of people asking for solutions to problems that they know are unsolvable. A famous example, is the 15 puzzle which you probably have played with one time or other. The goal is to slide the 15 squares around a square until they are in order.
I was always told that the great puzzle maker of the late 1880′s, Sam Loyd, created this puzzle. The current understanding is that he did not, and the puzzle was created by Noyes Chapman, the Postmaster of Canastota, New York. My sister-inlaw lives in Canastota, but that has nothing to do with this post.
The fun part of the puzzle is that a classic parity argument shows that the usual initial arrangement cannot be moved to the required final arrangement. The puzzle is unsolvable. The puzzle caused a “craze” during the late 1880′s. There were people who even thought they had solved the puzzle, but could not remember how. The best guess is pieces fell out of the puzzle, while they tried to solve it.
Role of Prizes
In the earlier history of mathematics, prizes for solving problems played a larger role than today. I have already talked about Henri Poincaré’s prize winning paper on the three-body problem. Erdös often offered money for the solution to open questions. He sometimes made the prize money quite asymmetric: a counter-example was worth $50 and proof was worth $500. I recall that one lucky solver won a prize of $1,000 for a very hard problem of Erdös and was asked was it worth it: he answered that he calculated that he made about 50¢ per hour.
Ron Graham used to manage Erdös’ money, including paying people who solved his open problems. Ron told me that at first most people kept the checks, probably framing them–this saved Ron the money. Then, people got color copier machines, so they could make a perfect copy, frame that, and then cash the check. Ron said that was okay, but what really got him was when some people started to cash the checks, and then asked for the cancelled checks back.
A final story about prizes concerns Jean-Paul Sartre, who won the Nobel prize for literature in 1964. Apparently he refused the Nobel prize, saying: “It is not the same thing if I sign Jean-Paul Sartre or if I sign Jean-Paul Sartre, Nobel Prize winner. A writer must refuse to allow himself to be transformed into an institution, even if it takes place in the most honorable form.” However, later he wrote a letter to the Nobel committee asking for the just the prize money; he was politely turned down.
Okay, the aliens have thrown down the challenge to find an algorithm for SAT. He is my best guess today for an approach. I would first use the powerful results from PCP that show that I “only” need to find an algorithm for 3-SAT that beats the trivial bound of satisfying of the clauses. The exact theorem that we are using is:
Theorem: Let . Suppose for satisfiable clauses of 3-SAT, there is a polynomial time algorithm that satisfies clauses, then P=NP.
Let be a set of 3-clauses that are satisfiable. I would then divides sets of clauses into two cases:
In this case I will assume that the clauses are “random.” This means that the clauses have enough “randomness”, in some sense, that the known algorithms that work well on random SAT can work on these clauses. I have no exact idea how to make this precise, but I hope you see the idea.
In this case I will assume that the clauses are not “random.” This means that there is some inherent structure to the clauses. I will hope that I can exploit this structure to show that there is a fast method for solving the SAT problem on structured clauses.
This randomness vs. structure is the idea that was used so brilliantly by Ben Green and Terry Tao in the recent famous proof of primes in arithmetic progressions. Perhaps we can use it on SAT.
The fundamental issue here is exactly what do I mean by “random” and “non-random”. The simple answer is that I do not yet have a precise notion. One way to approach this could be to try and characterize those clauses that the best SAT solvers fail on. If we could somehow understand what causes them to fail, then we would understand what “non-random” means in this context.
Then, we could attempt to show that for non-random clauses there is some additional properties that allow us to design an algorithm for such clauses.
The obvious question is can we make any progress on P=NP using this or some related approach. What I like about is two things. First, it uses one of the deepest results known in computational complexity–the PCP theorem. Second, it is looking for an algorithm, which we are good at finding. Just about every breakthrough in theory can be viewed as a new clever algorithm. This even holds for lower bounds. For example, the bounds on constant depth circuits are based on clever algorithms for approximating certain kinds of circuits by low degree polynomials.
Finally, if you get this to work, when you accept your Clay award and your million dollars please at least mention the blog.