## [Computational Complexity] Down to 100% sure that P\ne NP

Expand Messages
• In 1985 I was 120% sure that P ne NP. Why? Scott gave a nice list of reasons here. In 1988 I was down to 110% sure that P ne NP. Why? Because the Graph Minor
Message 1 of 1 , Jun 25, 2007
• 0 Attachment
In 1985 I was 120% sure that P\ne NP. Why? Scott gave a nice list of reasons here.

In 1988 I was down to 110% sure that P\ne NP. Why? Because the Graph Minor Theorem showed that many problems had faster algorithms than previously thought. Example:
For all g, Determining if a graph G is it of genus g. can be solved in O(n3) time (constant depends on g).
Note that the Graph Minor Theorem involves some very deep math. It took Robertson and Seymour many years to get the result. The papers are called Graph Minors I, Graph Minors II, etc. and in there someplace (perhaps around Graph minors XVII) is the graph minor theorem. I do not think that P=NP will be shown by using the Graph Minor Theorem; however, the fact that some very deep math lead to some problems having low complexity means that it could happen again, perhaps to SAT. Hence my confidence in P\ne NP went from 120% to 110%.

In 2007 I was down to 100% sure that P\ne NP. Why? Because Valiant used some strange techniques to solve the following problem in polynomial time.
Given a monotone boolean planar formula in 3-CNF form determine if the number of satisfying assignments is a multiple of 7. (NOTE- the problem for multiple-of-2 is Parity-P complete and hence NP-hard).
Again, a surprising algorithmic technique leads to problems being easier than we thought. To be fair, this is not a problem people looked at much (if at all). But the technique employed are truly new and my concern is that other truly new approaches may prove powerful enough to get SAT in P.

Neither NL closed under complementation nor Factoring in QP has made me lower by percent belief that P\ne NP. But they were surprising results and I can see someone else lowering theirs because of them.

So I'm down to 100% sure that P\ne NP. It will take a truly remarkable result for me to go lower than that. Like a polynomial time algorithm for SAT.

--
Posted By GASARCH to Computational Complexity at 6/25/2007 09:51:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.