Recently

Scott Posted an excellent essay on reasons to think that P NE NP. This inspired me to post on the same topic.

*Inspired *is probably the right word. Some of my post is copied and some of my post are my thoughts. A good test: if its intelligent and well thought out then its probably from Scott.

Why do scientists believe any particular theory? I state three reasons, though there are likely more:

(1) By doing Popperian experiments- experiments that really can fail. Their failure to fail helps to confirm the theory. This is common in Physics, though gets harder when the particles get smaller and string-like. (2) Great Explanatory power. Evolution is the main example here--- it's hard to do real experiments but one can look at the data that is already out there and find a theory that explains it all. (3) (Kuhn-light) It fits into the paradigm that scientists already have. This comes dangerously close to group think; however, if most of the people who have looked at problem X think Y, that should carry some weight.

Can we do Popperian experiments for P vs NP? For that matter can we do Popperian experiments in Mathematics? Goldbach's conjecture and the Riemann Hypothesis seem to have good empirical evidence. Though that kind of reasoning gets me nervous because of the following true story: Let li(x) = int_0^x dt/ln t.

Let pi(x) be the number of primes \le x. It is known that li(x) and pi(x) are VERY CLOSE. Empirical evidence suggested that li(x) \le pi(x) and this was conjectured. Skewes proved that there was an x for which li(x) \ge pi(x). His bound on x, the

the Skewes' number ,was quite large, at one time the largest number to appear in a math paper (that record now belongs to

Graham's Number). Then Littlewood, Skewes's advisor, showed that the sign of li(x)-pi(x) changes infinitely often. So the empirical evidence was not indicative.

There might also be empirical tests you can do for continuous math, especially if its related to physics so you can do physics experiments.

Have there been Popperian experiments to try to verify P NE NP? I am not quite sure what that means, but I do not think there have been (if I'm wrong please comment politely).

So we move on to

*Great Explanatory Power.* Are there many different empirical facts out there for which P NE NP would explain them and give a unifying reason? Does a bear... Well, never mind, the answer is YES! I give one examples (from Scott's post) and two more. But note that there are MANY MANY MORE.

- Set Cover problem: Given S_1,....S_m \subseteq {1,...,n} find the size of the smallest subset of S_1,...,S_m that covers the union of S_1,...,S_m. Chvatal showed in 1979 that one can find, i poly time, a subset of S_1,...,S_m that is (ln n)+OPT. Okay, great, an approximation. EMPIRICAL FACT: people seemed unable to improve on this at all. In 2013 Dana Moshkovitz proved that, assuming P\ne NP, this bound CANNOT be broken. Note that the algorithm of Chvatal and the lower bound of Moshkovitz have nothing to do with each other.
- Vertex cover: given a graph find the smallest set of vertices so that every edge has one of them as an endpoint. There is an algorthm that gives 2OPT. There is one that does ever so slightly better: (2-(1/sqrt(log V))OPT. In 2005 Dinur and Safra proved that, assuming P NE NP, there is no 1.36*OPT approximation. This does not match exactly but it still explains the lack of progress somewhat (more on this later when I discuss UQC).
- Max 3-SAT: given a 3-CNF formula find an assignment that maximizes the number of clauses satisfied. Karloff and Zwick proved that there is an algorithm that finds an assignment satisfying (7/8)*OPT. Hastad proved that, assuming P NE NP, (7/8)*OPT is the best you can do.

A bit more prosaic: P NE NP explains why people have had a hard time solving THOUSANDS OF PROBLEMS. I am most impressed with HAM CYCLE since mathematicians had been working on that one for quite some time--- trying to get a similar char to that of EULER circuit.

So in summary, I find that P NE NP has GREAT explanatory power. That makes it a very compelling conjecture. Let us apply this test to other conjectures.

- Sigma_2 \ne Pi_2. Does this assumption explain anything? Our inability to find a circuit for SAT. I dont know what else it implies. Same for Sigma_i vs Pi_i. This might qualify as mini-kuhnian: Sigma_2\ne Pi_2 fits into how we view the world.
- P=BPP. Almost every problem in BPP ended up falling into P over time. P=BPP would explain this. Also Nisan-Wigderson and its extensions make P=BPP fit into our world view.
- Unique Game Conjecture. This explains many upper and lower bounds that match, though nowhere near that of P NE NP. One of them is the constant 2 for VC. Even so, I find that compelling. (One of Scott's commenters said that all of the lower bounds from UGC are actually unified some how, so its not quite as compelling.)
- Factoring not in P. No real explanatory power here except that we seem to have a hard time finding an algorithm for Factoring.
- Graph Isom not in P. Similar to Factoring not in P.

So, what are our reasons to think Sigma_2 \ne Pi_2?

Lastly, mini-Kuhnian. What do people in the field think? The polls on P vs NP that I conducted in 2002 and 2012 (see

here) indicate that believe that P NE NP is growing- roughly 60% in 2002, roughly 80% in 2012. Some of the commentators on Scott's blog took that 20% of P=NP people to be relevant.

And indeed some of the P=NP people are both serious theorists and also not Dick Lipton (who seems to be who Lubos Motl points to) as a serious theorist who thinks P=NP).(ADDED LATER- SOME COMMENTERS HAVE INFORMED ME THAT LIPTON IS JUST OPEN TO THE POSS THAT P=NP. ) But some of those people emailed me that this was a protest vote, protesting the fields certainty that P=NP. I also note that three of them compared it to their voting or Ralph Nader in 2000, only with less drastic consequences.

I personally don't take `what people think' that seriously, but because of my polls we actually know what people think, so I put it out there.