Skip to content

Our Thoughts on P=NP

January 12, 2020


The Clay prize anniversary is soon.

SME keynote lecture source

Evelyn Lamb is a mathematician who is also a journalist. She has a blog called Roots of Unity on the Scientific American blog network. Also impressive is that she designed the AMS Page-a-Day Calendar on behalf of the American Mathematical Society. It is available from the AMS with member discounts and is filled with wonderful tidbits on math.

The other day she interviewed Ken and me on P=NP.

Ken just happened to be visiting me that afternoon in New York and we spoke to Evelyn about P=NP. The call was delayed because of equipment issues on both ends. Perhaps the fundamental problem is not P=NP after all, but making computerized equipment work. Oh well.

Evelyn is writing an article for the New Scientist magazine about P=NP. She said it was driven by the near 20th anniversary of the Clay Prizes. Recall there were seven of these, each with a million dollar prize. One, the Poincaré conjecture, was already solved. The others are still open—the million dollars is still there waiting for a brilliant researcher.

Questions and Answers

Here is our own rendition of some questions that came up. We did not keep a recording or notes on our end, and we have paraphrased and expanded some things that we said:

{\bullet } What is the update on P=NP?

Ken: The update is that here is no update. There is no recent progress on resolving P=NP—seemingly none this decade, I’d say. This is still light-years away from it and you could even say the difficulty needed for yea-much progress is discouraging. There are some conjectures that elaborate on P {\neq} NP, including Unique Games and (S)ETH, but those two have gone less clear.


{\bullet } Does the Clay prize help researchers?

Dick: I do not see that the prize gets anyone to work on P=NP.
Ken: I disagree. The prize does help people explain quickly what they are working on to others and why. This is quite valuable.


{\bullet } Could P=NP be undecidable?

Dick: Who knows. I note that known proofs that some combinatorial problem is unprovable in Peano arithmetic somehow rely on a function that grows too fast. The famous Ramsey problem is a perfect example. I do not see any way to get such a function in the P=NP area. Of course I could easily be wrong.

Ken: This is the subject by which Dick and I first came to know each other in the 1980s, for instance this paper of Dick’s with Rich DeMillo vis-à-vis one of mine. I now believe it is resolvable but will need deep and complex techniques.


Here I, Ken, went into the topic of “Natural Proofs,” as Dick did again later.


{\bullet } When will P=NP be solved?

Ken: We just discussed this on our blog. The upshot is that the conjecture has been open long enough—coming to its 50th anniversary if you date it by Steve Cook’s famous 1970–71 paper, 64 years if you date it by Kurt Gödel’s 1956 letter to John von Neumann—that it is going outside the range where data on other conjectures has any predictive value.

Dick: There is a related issue with P=NP. Perhaps we have guessed the wrong direction. Most believe that P is not equal to NP. But many conjectures were finally resolved when someone worked on the right direction.


{\bullet } Who believes P=NP vs P {\neq} NP?

Ken: Our friend Bill Gasarch has polled this three times since 2002. His article finds 80% support for P {\neq} NP, which he says goes higher among those who have worked more on it. I believe unequal, but Dick’s opinion is fluid and Don Knuth recently said he takes the “equal” possibility seriously.


I (Ken) started hunting for how we’ve covered Knuth’s opinion on GLL—it seems only a brief mention here and in comments here—but Dick related hearing it in person from Knuth.


{\bullet } Why so Hard?

Ken: If you believe P {\neq} NP, then it is hard because Nature—mathematical nature—does a bang-up job of making it seem like P {=} NP. Most instances of NP-complete problems are easy; so called SAT-solvers have had much practical success. The larger issue is that nature has frustrated us from proving any nontrivial general lower bounds at all. You can allow a {2^{O(n)}} exponential-time algorithm to make exponentially-long queries to NP and yet no one has proved that the resulting language cannot be decided by linear-sized Boolean circuits. Ryan Williams needed a lot of effort to prove that this class does not have constant-depth poly-size modular-counting circuits, but those could be weaker in relevant ways than general linear-size circuits. But this class is a lot bigger than NP.


I then said another factor is that sometimes algorithms seem to make no visible progress until at the very end when they suddenly come up with a correct answer. Dick and I had tried to quantify a notion of progress. I then started talking about the “hardness versus randomness” phenomenon and the “Natural Proofs” barrier again (for which this 2016 paper by Ryan is a good reference) but Dick cut in with a nub of all these matters.

Dick: A key issue is what I call “Bait-and-Switch” (indeed, in a post on the first day of GLL). Suppose an output {x} is believed to be hard. Add a random {y} to it. The result {z} is also random. One branch of an algorithm computing {y} and another working on {z} seem to have nothing to do with {x}. Yet when you do {y+z} bitwise you have {x}. This destroys any lower-bound argument that would be based on metering progress toward {x}.


{\bullet } Guessing wrong way?

Dick continued saying that this issue only affects the “not equal” position and maybe it’s a hint of people guessing the wrong way. This went back into some things that were said before, and then the call started winding up.

Things We Didn’t Say

We had made mental notes while walking back from lunch across the street in time for the call, but forgot some of them. To recycle an old saying, a mental note isn’t worth the paper it’s written on.

One of them was to remark on Gerhard Woeginger’s P Versus NP claims page and the relative balance of claims of “Equal” and “Not equal.” As of its last update in September 2016, the 116 listed claims are (by Ken’s count) divided 62 for “Equal,” 49 for “Not equal,” 3 for unprovable/undecidable, 1 claiming no claim, and 1 for both “Equal” and “Not equal.” It may be that “Equal” predominates because its logical formula begins with {\exists} and it seems easier to imagine one has found a single {X} that works rather than to exclude all {X}—an infinite number of them.

I (Ken) had intended to connect this and the P=NP poll results to our post two months ago about cases of open questions where one direction seems overwhelmingly supported both by evidence and sentiment. Whatever one thinks about the value of all the P-vs.-NP claims, they witness that P-vs.-NP is certainly not one of those cases.

Last, I had intended to mention the deepest evidence in favor of “not equal.” This is the sinuous thin line between hard and easy cases of problems. Going back at least to Thomas Schaefer’s great 1978 work classifying cases of SAT, we’ve been aware of a surprisingly sharp dichotomy between “hard” and “in P” with seemingly no buffer zone. And the line sometimes seems to fall capriciously. In the second half of this post we mentioned Jin-Yi Cai’s work on dichotomy and a case relevant also to quantum where counting solutions to a fixed family of quadratic mod-4 polynomials in {\{0,1,2,3\}^n} is easy, but counting those in {\{0,1\}^n} to the same polynomial is hard. For another instance of this widely-appreciated point, see Scott Aaronson’s discussion of 3SAT here.

The point is that if P=NP (or counting is in P) then all of this finely filigreed structure would vanish—poof—an illusion all along. Like if the Mandelbrot Set became a smeary blob. But then we’d be left with: why did we have this illusion in the first place?

Open Problems

We suggested that she speak to some others—people more expert than we are. For this and other reasons the article may be quite different. We hope giving our own summary here is a help. What points would you add to it?

We also forgot to ask her about her own work in Teichmüller theory. Here are a couple of her articles on the ABC Conjecture. But that is not a Clay problem and is a subject for another decade.

[Edited 50 to 20]

17 Comments leave one →
  1. January 12, 2020 6:21 pm

    See the answer here:

    https://zenodo.org/record/3605338

  2. January 13, 2020 3:22 am

    What points would you add to it?

    I would add the problem presented by the Institute to win the prize: “Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.”

    1. How do I put together a list of 50 pairs of compatible students?
    2. Are all the students on the list of incompatible pairs?
    If this is not the case, I make a distinction between problematic-unproblematic students, where the problematic ones are those who are on the list of incompatible pairs and the unproblematic ones are those who are not on this list. Note that I have created a new list of unproblematic students and renamed the list of incompatible pairs as problematic.
    3. Who are the unproblematic students? They are those who have no problems with anyone and no one has a problem with them. There must be at least one student who is not on the list of incompatible pairs.
    4. What to do now? Add students from the other list (problematic) to the list of unproblematic students until 50 pairs of compatible students are formed. When they move to the new list they lose their “problematic” character because the pairs of incompatible students they were part of are broken.
    5. So: If I have 100 unproblematic students, then I have the list of 50 compatible pairs.
    If I have 90, then I only need 10 students from the other list to complete the pairs.
    If I have 80, then I only need 20.
    If 70-30
    If 60-40
    If 50-50
    If 40-60
    If 30-70
    If 20-80
    If 10-90
    If 1-99.

    Thanks for the space and attention.

    • August 16, 2020 6:57 pm

      Important: The third set created by the distinction can also be an empty set. This does not prevent the operation of addition for forming 50 pairs of compatible students.

      And a speculative question: What strange force would attract certain elements to an empty set and order them? The opposite seems simpler…

      See https://twitter.com/joyce1

  3. Geoffrey Irving permalink
    January 13, 2020 4:34 am

    A minor comment: the reply to “Could P=NP be undecidable?” answers a different question, namely “Could P=NP be proven undecidable?” This is a common substitution, but it seems treacherous when reasoning about the undecidability of statements to replace “true” with “provable”.

    • January 15, 2020 12:34 am

      Great point. This is a bit of a thicket. If P!=NP were like Riemann or Goldbach in terms of being provably refutable if false, then proving it undecidable would prove it true. There once was a serious claim of this. This was a last-minute edit from Dick’s original “unprovable” to “undecidable” because the sentence then seems to vote on P=NP versus P!=NP, whereas the post means “P=NP” as the problem. Dick’s reply is addressing one part of this thicket. My quoted reply is instead taking “undecidable” in the human modal sense: are we never going to resolve it?

  4. Wolfgang Keller permalink
    January 13, 2020 8:22 am

    > She said it was driven by the near 50th anniversary of the Clay Prizes.

    I think you rather mean 20th anniversary.

    • rjlipton permalink*
      January 13, 2020 9:18 am

      Dear Wolfgang Keller:

      Oh my…I think you are right. I tried to see if we could argue we meant 20 in another radix, but even in radix 6 we are way too high. Thanks for the catch.

      Best

      Dick

    • January 15, 2020 12:35 am

      This was also a last-minute edit—missed by both of us while conflating with the 50th anniversary of Cook’s paper.

  5. January 14, 2020 3:52 pm

    If it is indeed P≠NP, it means that NP is completely different from P, in other words, the P vs NP problem may involve some important conceptual issues.

    Maybe we can question about the two current definitions of NP (NP is verifiable; NP is decidable) : Whether do the two definitions capture the essence of NP?

  6. January 14, 2020 4:23 pm

    If it is indeed P≠NP, it means that NP is different from P, in other word, the P vs NP problem may involve some important conceptual issues.

    Therefore, we can question about the definitions of NP : whether do they capture the essence of NP?

  7. Ricardo Mota Gomes permalink
    March 21, 2020 5:27 pm

    p = np non existence of way-one functions is true

  8. Ricardo Mota Gomes permalink
    March 21, 2020 6:24 pm

    P = NP “” Non existence of one-way functions is true

    • Ricardo Mota Gomes permalink
      March 21, 2020 6:30 pm

      P = NP se e somente se a inexistência de funções de sentido único é verdadeira !!! …

Trackbacks

  1. Halting Is Poly-Time Quantum Provable | Gödel's Lost Letter and P=NP
  2. Predicting Predictions For the 20s | Gödel's Lost Letter and P=NP
  3. Newsletter NSSN nº8 – Not So Short Notes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s