Monday, March 10, 2014

Why do we think P NE NP? (inspired by Scott's post)

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.

  1. 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.
  2. 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).
  3. 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.

  1. 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.
  2. 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.
  3. 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.)
  4. Factoring not in P. No real explanatory power here except that we seem to have a hard time finding an algorithm for Factoring. 
  5. 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.


  1. "also not Dick Lipton (who seems to be who everyone points to) as a serious theorist who thinks P=NP" - while I'm not sure this sentence makes sense grammatically, I would also argue its truth. IMHO Lipton thinks P=NP is possible, which is not the same as thinking P=NP. I also think that P=NP is possible but if I had to guess, I would guess there are not equal.

  2. Håstad, not Hastad.

  3. I agree with Dom. Having taken Lipton's course, I remember him saying that "for the right odds" he would be willing to bet that P=NP... that's a far cry from thinking that P=NP. One concrete thing he said was that it's debatable whether all the NP-complete problems should be considered independent problems or just versions of one problem.

  4. Well, since you are all expressing it in terms of odds and possibilities, what do the bookies in London say? What odds are they giving?

  5. Theorem: P=NP <==> P!=NP.

    Proof: The Kleene-Rosser paradox is a counter-example to NP-completeness.


    Step 1. Cook_Levin: For all w in L in NP,
    M accepts w <==> \exists A(w)=SAT.

    Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
    M_KR accepts w_KR <==> e^-1(w_KR)= NOT e^-1(w_KR).

    Step 3. Put M=M_KR and w=w_KR.

    ==> L.H.S. of (1) = L.H.S. of (2).

    ==> R.H.S. of (1) = R.H.S. of (2).

    ==> There is no SAT(w_KR).

    ==> L_KR={w_KR_i} is in NP and NOT NP-complete.

    ==> L_KR is a counter-example for NP-completeness.

    ==> SAT is (NOT) NP-complete.

    ==> SAT is NP-complete <==> SAT is (NOT) NP-complete,
    Cook's proof is still correct despite the contradiction.

    ==> P=NP <==> P!=NP.


    Rafee Kamouna.

  6. Just to clarify the result about set cover hardness, in an APPROX 2012 paper Moshkovitz showed that if a certain conjecture was true, then it is NP-hard to approximate set cover within ln n. In an upcoming STOC 2014 paper, Dinur and Steurer show (among other results) that a weakened form of the conjecture is true, and this is enough to imply the set cover result. The Moshkovitz paper which is pointed to in the blog post is a recently updated version of the APPROX paper which now notes that the result of the Dinur-Steurer paper allows the proof of the result.

    1. Ya, what is the story here? Dinur and Steurer also claim the set cover result as their own, and their arxiv paper ( is from May, which significantly predates Dana's December revision.

    2. My understanding is that, as David said, Dana proved the result modulo one missing piece in 2011 ( Dinur and Steurer later filled in the missing piece. The paper Gasarch linked to is the journal version of Dana's paper, which explains the whole history and which credits Dinur-Steurer.

  7. It took 350 years for FLT to be proven. New math was invented trying to prove it. One clever approach that has not yet been considered ends it all.

  8. Reasons associated to the (plausible) undecidability of PvsNP are summarized in the following TCS StackExchange answer:

    • "Are runtime bounds in P decidable? (answer: no)"

    and in the following TCS StackExchange community wikis:

    • "Does P contain languages whose existence is independent of PA or ZFC? (answer: not known)"

    • "Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)"

    As Scott Aaronson aptly says "The border [between complexity classes] traces out weird and jagged shapes." To the best of present complexity-theoretic knowledge, the "shape" of the borders between oracle-defined complexity classes plausibly is so "weird and jagged" that (in general) class membership is undecidable.

    1. Postscript  In particular, the TCS StackExchange question Does P contain languages whose existence is independent of PA or ZFC? (answer: not known) was converted to an open community wiki precisely to encourage sustained mathematical discourse relating to PvsNP, regarding which the opinions of complexity theorists have been so notably (and wonderfully!) diverse for two generations.

      A respectable cohort of CT luminaries already has commented upon the above question, and further comments (and even entire proposed answers) are welcomed needless to say.

      So if you've got an answer, post it!

      It was Scott Aaronson who suggested TCS StackExchange as an appropriate venue for open, reasoned, civil discussions of PvsNP questions. That was well done, Scott.

    2. Followup  The above considerations have been formulated as one answer (of several posted) to Scott Aaronson's MathOverflow question/request for "Analogues of P vs. NP in the history of mathematics,", that answer being:

      The Runtime Fence Problem for TMs  which Emanuele Viola proved is undecidable, and by extension

      The Runtime Fence Problem for Languages  which is natural, open, apparently difficult, and conjecturally undecidable.

      Computational Complexity readers who can supply further answers to Scott's well-asked question/request, please post them.

  9. What is your opinion of Paradox Recognition:

    1. decidable.
    2. Semi-decidable.
    3. Undecidable.
    4. Paradoxical.

    Established belief since the 1930s is that it is an undecidable.problem, while any student kid can write a trivial program to decide it. This is why Scott is banning the above proof.


    Rafee Kamouna.

  10. Just like Dr Lipton, I am also "just open" to the possibility P=NP, saying that its chances and those of P!=NP should be taken comparable if one is not prejudiced. This is also how my view was (correctly) represented by Scott Aaronson (in his otherwise demagogic, untrue, insulting, and generally idiotic rant).

  11. I still like to think about these sorts of problems regardless because they do form something to think about to generate ideas. One thing that is fun to think about is that while it is hard to find the best path, it is relatively easy to find a least squares circle that passes by each point such that the residuals can be minimized. One can think also in terms of projections on independent axis, which automatically has an ordering on that axis. There are all sorts of ways to look at the problem that make the problem interesting to think about if not work on, which is probably why it gets a lot of interest, even if some of the claims about what P=NP would mean are overstated some times.


    1. Sorry for the late response- I was just browing this old post for some reason and came upon your comment that I must have missed back in 2017.
      Anyway, I think the problem of amicable numbers- given x,y
      is it the case that the factors of x add up to y and vice versa
      was in BPP but I THINK is now in P.

      however, the fact that this is the ONE problem I can think of and I may even be wrong shows that YES, there are VERY FEW
      problems in BPP in the first place.

  13. Dear William Gasarch,

    Happy New Year!

    Since you talk of « Kuhn-light », we may look at the P vs NP problem from another perspective :

    There exist mainly two opinions about the P vs NP problem: P = NP and P /= NP (P NE NP), and most people think P /= NP (see Gasarch’s second poll [1]).

    As known, there exist two popular definitions of NP which are considered to be equivalent [2][3] :
    Definition 1 : NP is the class of problems decidable by NDTM (NonDeterminisitic Turing Machine) in polynomial time.
    Definition 2 : NP is the class of problems verifiable by TM (Turing Machine) in polynomial time.

    If it is indeed P /= NP, it means that NP is completely different from P, then the P vs NP problem may involve some profound conceptual issues. Therefore, we can ask:
    Are these two popular definitions of NP consistent with the reality?

    In other words, we ask:
    Q1: What is NP?
    Q2: Can « NP is the class of problems decidable by NDTM in polynomial time » be the definition of NP?
    Q3: Can « NP is the class of problems verifiable by TM in polynomial time » be the definition of NP?

    Yu LI

    Reference :
    [1] William I. Gasarch, The P=?NP poll. SIGACT News Complexity Theory Column 74.
    [3] Sipser's Introduction to the Theory of Computation, section 7.3.