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(n^{3}) 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