Skip to content

P=NP Proofs

April 21, 2019


Advice to claimers

The Claimers

The Claimers are a gang on the hit AMC television series The Walking Dead. They are the main antagonists in the second half of the zombie-apocalypse show’s Season 4. According to Wikipedia’s description, they “live by the philosophy of ‘claiming’.”

Today Ken and I discuss issues about ‘claiming’ and give advice on how to present your claims—or not.

Yes, this post is about our own “claimers” in complexity theory. It is especially about those who claim to have a solution to P=NP. We will not give any names today. You know who you are.

The TV Claimers meet a grisly end. We will not say any more about it. We want to be nice. But we would like to not keep seeing the same level of zombie claims raised again and again.

Please: Do not stop reading. Yes we know that it is likely that no claimer really has such a proof. However, our suggestions apply to all of us when we have a non-trivial result. Especially a result that has been open, even if the result is not a major open problem. So please keep reading today.

So You Can Prove P=NP

This is a list of ideas for anyone who claims to have solved P=NP or some similar hard open problem in mathematics. There are already lots of suggestions online about what you should do, so this is just a list of additional thoughts. We hope they are helpful.

You are being pretty arrogant

In order to succeed in mathematics research one has to be a bit arrogant. It is quite difficult to prove new things without some swagger. However, proving or resolving P=NP requires a very non-humble attitude. I think many claimers have not thought how arrogant they are being. The P=NP problem is a huge open problem. Thousands and thousands of researchers have spent years thinking about it. Why do you, the claimer, think you see the light and we remain in the dark?

It might be useful for the claimers to ponder: Why did I succeed where all others have failed? It might be useful to be a bit humble and at least think what did they see that we all missed? If they can say something like:

The reason I succeeded in finding an algorithm for P=NP is that I noticed that {\dots} No one else seems to see that this insight is very powerful. It is very useful since it implies {\dots}

Working alone

I think the vast majority of claimers of P=NP or other big results have almost always worked alone. This is okay, but the average number of authors these days of a theory paper is pretty large. So any paper that is sole authored, perhaps, leads the community think it is unusual—and is wrong. Another point is that being part of a team may help control the arrogance. It can also be invaluable in detecting errors.

Show them the money

There is an advantage in “proving” P=NP over other major problems. There is the Clay prize of a million dollars. I wonder if claimers could use the prize money in some interesting way. How about saying: If you read the my proof and repair it or make it more readable and it is correct, then you get something. A certain dollar amount. Or a percentage of the prize. Or—you get the idea.

The role of code

Many claimers have also supplied working code for their algorithm. That is they also supply a program that claims to solve some NP-complete problem. I have several thoughts about this. In some cases it seems that it could be possible to have code that works for small size problems, but not in the general case. This seems to be possible for the claims by some that they can solve the Traveling Salesman Problem, for example. Their algorithm could be correct for small instances.

Mathematics is filled with surprises like: This effect works for all values of {X} less than some bound. If the claimers give a program, our expectation based on experience is that it may work for small cases but will probably fail in general.

The last point is that working code could actually be valuable. If the code can be used to solve SAT problems how about using your program to enter a SAT contest and win it. A win, or even a good showing, would help tremendously in convincing people to read the paper. Or use the code to break some known cryptosystem. That would also convince people that they need to read your paper.

Writing Your Paper

Okay we all dream about solving a major open problem. Or even a minor one. Here we give an outline of how to write up such a paper.

How to write up the proof

I would suggest that you not have any statements about why P=NP is an important problem. None. No history of the problem. No literature survey is needed. None. You goal is to get an expert to read and believe the proof. They will just skip over the above. Also please no statements of how your algorithm that solves P=NP is going to change the world. Just give us the proof.

How to get them to read the proof

This is really hard. Hard. I have read a number of claimers’ papers. I try to be helpful. However, many of us do not have the time to look at such papers. Years ago, before Fermat’s Last Theorem was solved, a famous mathematician once made up a post-card that looked like this:

I think that we all have a mental version of this card. There are definitely ways to help induce someone to read a paper and its proof. Look at some recent top theory papers. Even the authors of these papers, often well known authors, work hard to motivate potential readers. The authors often do several things:

{\bullet } They often sketch the proof. By leaving out details they may help get a reader interested.

{\bullet } They often explain the new trick—or tricks. The goal here is to explain some new insight that is used in the proof. We are very self-oriented: If I see that your new trick could be useful in my research that is a huge motivator for me to understand the proof. People are very excited about a strong result, but they are even more excited about a new trick. Explain what is new in your proof. If there is nothing new, no new trick or method, then hmmmm{\dots}

{\bullet } They often first prove a weaker result. That is, they show that their method can already make progress. If you could prove that the zeta function has all its nontrivial zeros on the critical line, that would be apocalyptic—the famous Riemann Hypothesis, of course. But if you could merely prove that there is no zero in some new region, then that would still be wonderful. And also probably more believable. If you could prove that there is no zero {z} with its real part {0.99999} that would be huge. If the proof of this is simpler, then use it to get readers excited about your full result.

An observation related to the last point is:

Why do all claims of progress on P=NP give a polynomial time bound?

How about just getting a better bound of say {2^{n/10}} for the Traveling Salesman Problem? Or a better bound for factoring? Or a better bound for your favorite problem?

Open Problems

I hope these points help. One last pointer is to double-check dependencies. If your proof relies on a result by someone else, make sure the result really gives what you need. Terms may be defined differently from what you expect, or you may really need a feature of the proof rather than the mere statement. A mis-attributed result can become “undead.”

Advertisements
30 Comments leave one →
  1. Bhupinder Singh Anand permalink
    April 22, 2019 1:12 am

    Well, the reason I believe I have succeeded in showing that—contrary to conventional wisdom—the prime divisors of an integer are mutually independent is that (see Ref. 1) I noticed there is an, hitherto unsuspected, distinction between algorithmically computable arithmetical reasoning based on algorithmically computable arithmetical truth, and algorithmically verifiable arithmetical reasoning based on algorithmically verifiable arithmetical truth. This insight is very powerful for arguing that Integer Factorisation cannot be polynomial time (see Ref. 2).

    Ref. 1: `The truth assignments that differentiate human reasoning from mechanistic reasoning: The evidence-based argument for Lucas’ Goedelian thesis’

    https://www.sciencedirect.com/science/article/pii/S1389041716300250?via%3Dihub

    The paper appeared in the December 2016 issue of ‘Cognitive Systems Research’, and introduces evidence-based reasoning, which addresses the philosophical challenge that arises when an intelligence—whether human or mechanistic—accepts arithmetical propositions as true under an interpretation—either axiomatically or on the basis of subjective self-evidence—without any specified methodology for objectively evidencing such acceptance

    Ref. 2: ‘Are the prime divisors of an integer mutually independent? Why Integer Factorising cannot be polynomial-time’

    https://www.dropbox.com/s/4q57dca9zo6gz84/39_Anand_Dogmas_Prime_Divisors_Update.pdf?dl=0

    A follow-up investigation to Ref. 1, which uses evidence-based reasoning to show that, and why, the prime divisors of an integer are mutually independent. It then shows how this immediately entails that determining whether the signature of a given integer n—coded as the key in a combination lock—is that of a prime, or not, can be done in polynomial time. It finally argues the hypothesis that determining a factor of a given integer n cannot be polynomial time.

  2. Anon permalink
    April 22, 2019 7:53 am

    Another (more modern) option to get attention for a proposed proof would be to formalize the proof in a proof assistant. This would likely be a fair amount of work, but would certainly provide strong evidence!

    • rjlipton permalink*
      April 22, 2019 8:20 am

      Thanks

      It is an approach that has been taken even by mainstream mathematicians. Thomas Hales used this on his packing theorem.

      Best

    • rjlipton permalink*
      April 22, 2019 8:17 am

      Thanks…
      I totally agree with your comments

      Best

  3. kamouna permalink
    April 22, 2019 8:42 am

    State the Cook-Levin theorem for a paradoxical input, you get a counter-example to the theorem and SAT is NP-complete iff SAT is not NP-complete.

    \forall w\in L\in NP \exists A(w)=SAT iff M accepts w iff e^-1(w)=NOT e^-1(w)

    ==> there is no A(w)=SAT and SAT is not NP-complete.

    Best,

    Rafee Kamouna.

  4. anon permalink
    April 22, 2019 12:18 pm

    Scott Aaronson, 10 signs that a claimed mathematical breakthrough is wrong: https://www.scottaaronson.com/blog/?p=304

    Terry Tao, Editorial policy on submissions concerning famous problems (scroll down): https://www.math.ucla.edu/~tao/submissions.html

    Both of the above seem cogent.

    • rjlipton permalink*
      April 22, 2019 1:05 pm

      Dear anon

      Yes I like Scott’s insights and same of course for Tao’s. I like Tao’s suggestion to seek out some help. It is quite possible to find a friendly person who might be able to help a claimer. This is not—however—a suggestion that Ken or I are ready to help anyone right now.

      Best

  5. samurai49 permalink
    April 22, 2019 12:42 pm

    I don’t think to work alone, and claiming a new proof is arrogant. Difficult problems such as Fermat’s Last Theorem and Poincare Conjecture, were solved by people who have worked alone for many years. It is just really a lot of deep work, that requires a lot of concentration, which does require isolation. Solving P=NP is one of those types of problems.

    • rjlipton permalink*
      April 22, 2019 2:14 pm

      Dear samurai49:

      I do agree with you that often big problems have been solved by a single author. Of course
      these authors do then rely on the community to help look at the proof. FLT is a perfect
      example of that.

      Thanks for your comment

      Best

  6. Ben Samuel permalink
    April 22, 2019 2:23 pm

    I have a marvelous proof that P=NP, but unfortunately it’s too large to write in the comments here.

    • rjlipton permalink*
      April 22, 2019 4:16 pm

      Dear Ben Samuel:

      I heard something like that before. Does point out the way things have changed over the years. I do recall tight pages limits on authors for conferences like STOC/FOCS especially.

      Best

  7. April 23, 2019 6:17 am

    Nice suggestions, but will it really help a claimer if he follows them? Take Mathias Hauptmann’s proof of P!=NP for example. He seems to follow every suggestion from “How to write up the proof” and “How to get them to read the proof”, except for “first prove a weaker result”. No history of the problem, just the proof. And he sketches the proof and explains the new trick-or tricks. I have not heard any news of Mathias Hauptmann since he published a preprint of his proof. Hmm…

    Or take the recent analog (max)SAT solvers. They did follow the “The role of code” suggestion, and use their code to compete against state of the art solvers. Looks like their startup is doing reasonably well, so why bother just now? In the end, judging borderline cases is hard, and why should anyone spend his valuable time on demolishing other people’s “achievements”!

    • rjlipton permalink*
      April 23, 2019 9:35 am

      Dear gentzen

      I agree that Mathias Hauptmann’s proof is a potential counterexample to what we suggest. He does follow much of our advice and yet his proof that P is not equal to NP seems just out there. This lead me to think some more about why we check proofs. More in the future.

      Thanks again for your thoughtful comment.

      Best

  8. William Gasarch permalink
    April 23, 2019 11:01 am

    You are being a bit too nice to the claimers. I used to think that `even if this proof that P=NP is wrong maybe they have a really good SAT solver’ Never. Or `even if this proof that P NE NP is wrong maybe they have some weak lower bound.’ Never. Oh well.

    • rjlipton permalink*
      April 23, 2019 3:01 pm

      Dear Bill:

      Yes it is still all or nothing for both P=NP and P not equal NP. I do find it interesting that for P vs NP and many other open problems, claimers seem always to claim it all. I have yet to see a claim that SAT requires super linear time. As you say…Oh well.

      Best

  9. James Candy permalink
    April 24, 2019 2:33 pm

    I’ve been looking at P vs. NP from a couple different directions. On the P=NP side, I’ve considered that standard algorithms such as CDCL may have probabilistic arguments showing they are efficient (on average) for very large input sizes. On the P/=NP side, I’m looking at using a method of diagonalization combined with compressed encoding. The way this works, is to construct a family of languages which individually diagonalize P[n^k] for all k (the class of languages solveable in polynomial time of order k). Then I try to find a “compressed” representation of these languages in NP.

    I think this picture is analogous to the picture with respect to decidability. On the one hand, it’s possible to determine the truth or falsehood of the average mathematical statement (with a certain probability of success) by an inductive machine, but on the other, some statements are always independent of the formal system, specifically ones constructed by diagonalization.

    • rjlipton permalink*
      April 24, 2019 6:16 pm

      Dear Candy:

      I like that you are thinking about P=NP and P!=NP. I have in much more modest situations been fooled by guessing the wrong way. Once I thought about the right direction I was successful. Not sure what you mean by “inductive machine”?

      Best and good luck

Trackbacks

  1. New top story on Hacker News: P=NP Proofs – Advice to Claimers – Outside The Know
  2. New top story on Hacker News: P=NP Proofs – Advice to Claimers – World Best News
  3. New top story on Hacker News: P=NP Proofs – Advice to Claimers – Latest news
  4. New top story on Hacker News: P=NP Proofs – Advice to Claimers – Hckr News
  5. New top story on Hacker News: P=NP Proofs – Advice to Claimers – News about world
  6. P=NP Proofs – Advice to claimers | My Tech Blog
  7. P=NP Proofs – JNW
  8. The Claimers – The nth Root
  9. P = NP Proofs: Advice to claimers | My Tech Blog
  10. Why Check A Proof? | Gödel's Lost Letter and P=NP
  11. Resumen de lecturas compartidas durante abril de 2019 | Vestigium

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