Like most complexity theorists, I strongly believe that P is not equal to NP, i.e., it is harder to search for a solution than verify it. Let me quote Juris Hartmanis in 1985, "We know that P is different from NP, we just don't know how to prove it."

**We are further away from showing P ≠ NP then we have ever
been.** Let me explain this. In 1985 when I started graduate school,
computational complexity theorists were in the midst of showing newer
and stronger lower bounds on circuits. Furst, Saxe and Sipser in 1983
gave the first nontrivial lower bounds on bounded-depth circuits. In
1985, Yao followed soon after by stronger results of Hastad, gave
exponential lower bounds. In 1986, Razborov showed that clique does
not have small monotone circuits. In 1987, Razborov and Smolensky
showed that parity could not be computed on bounded-depth circuits
with Mod_{3} gates. It seemed to many complexity theorists
that the separation of P and NP was right around the corner.

But circuit lower bounds hit a brick wall. We have seen no significant progress on non-monotone circuit lower bounds since 1987. We have seen some new lower bounds in the past few years, using proposition proof complexity, branching programs, algebraic geometry and old-fashioned diagonalization, but all of these results are in models far too weak to even approach the complexity of the P versus NP question.

Settling the P versus NP question might require some branch of mathematics not even invented yet and that I would never have a prayer of understanding even the idea of the proof. When it will be proven cannot be predicted at all--it could be within a few years or maybe not in the next five hundred. It all depends on how long it will take to come up with the right new idea.

There are as many opinions on the future of the P versus NP question as there are theorists. Bill Gasarch has collected many of these opinions. It makes for an interesting read but you might as well ask Miss Cleo.

It is possible that P = NP is independent of the axioms of set theory. Doubtful I say, but that is a topic for another post.

## No comments:

## Post a Comment