Skip to content

Code It Up

August 6, 2019


So you think you have a proof that P=NP

Randi 2014 documentary source

James Randi is a magician who has challenged paranormal claims of all kinds.

Today Ken and I want to make a suggestion to those who claim they have proved P=NP.

No the claim to have a proof that P=NP is not a paranormal claim. But such claims are related to Randi—or the Amazing Randi as he is called. We talked about him before here.

Randi once helped run a contest to see who could find gold with their dowsing rod. He explained why he doubted one contestant:

If they really could find gold, why were they dressed so poorly, and why were they so interested in winning the prize?

I have the same question about those who claim that they have a proof that P=NP. Usually the proof is constructive and I agree with Randi:

If they really could solve P=NP, why {\dots}

You get the idea.

Ken adds the obvious remark that if a foreign power or intelligence agency discovered P=NP, or factoring in P, they would still keep the lean-and-hungry look. But they are not the kind we are addressing here.

Coding Helps

Let’s look at a claims that P=NP is resolved. Yes, such a result is unlikely—many would say impossible. But we do get claims like this:

The following {\cal H} is known to be a NP-complete problem; the following {\cal E} is known to be a polynomial time problem. I can reduce {\cal H} to {\cal E} in polynomial time.

Usually the reduction is the reason their proof fails. Their claims about {\cal H} and {\cal E} are usually correct, since they are in the literature.

The reduction is often complicated, often poorly defined, often defined by example. Giving a precise definition for the reduction is critical. This is the reason we suggest the following:

Write the reduction down in code.

Even better, write it as a program in a real language such as Python.

There are two advantages in doing this.

  • Writing it as a program in a real language will likely force one to define it precisely.

  • Writing it down will also allow one to run the program on examples.

The later point is the key point. Even trying your method on tiny examples is useful. Even better if you can say the following we might read the proof:

I have tried my code on the following public set of difficult SAT problems. The code solved all in less than three minutes each.

This claim would greatly improve the likelihood that people might take your claims seriously. That your code worked correctly, forgetting the running time, would improve confidence. Greatly.

The Animal Farm View{\dots}

Ken worries that some NP-complete problems are more equal than others. That is some problems, even though they are NP-complete may require reductions that blow up when encoding SAT.

We wrote about this before regarding the “Power Index” idea of Richard Stearns and Harry Hunt III. In their paper they gave evidence that the reductions from SAT to many familiar NP-complete problems must expand the size of instances quadratically, insofar as those problems have power index {0.5}. This was based on their “SAT Hypothesis” which anticipated current forms of the Exponential Time Hypothesis, which we have discussed.

Ken ponders a related issue. Even problems with power index {1} run into the success of practical solvers. This means:

Anyone citing algorithmic success as evidence toward a claim of P=NP must compete with the real-world success of algorithms that do not represent claims of P=NP.

We have several times discussed the practical success of SAT-solvers on myriad real-world instances.

This situation has become real in the argument over achieving quantum supremacy. One who claims that quantum is superior to classic must worry that that classical algorithms can improve without making P=NP. A headline example from last year was when Ewin Tang—as a high-school senior—found a classical way to remove a plausible quantum advantage in a matrix-completion problem that underlies recommender systems. There are many “industrial strength” examples in this argument—see this May 2019 story for a start.

But…

Ken’s insightful comments aside, the key point is still:

Coding up your claimed algorithm for that NP-complete problem will still enhance belief.

This will happen even if the algorithm only succeeds on tiny examples. Indeed, if you cannot do this then I suggest that you will have an impossible time getting anyone to listen.

Open Problems

How useful is this advice for the vast majority of us who are not claiming P=NP or the opposite?

Advertisements
60 Comments leave one →
  1. August 6, 2019 5:20 pm

    But….

    What if the algorithms are shown as a pseudocode in a claim paper?

    And…

    What if the algorithms are so easy to follow that even a undergraduate student could understand them in a claim paper?

    And…

    What if the algorithms could be programmed even by a teenage maybe in Python after reading a claim paper?

    Then…

    What if that claim paper is this one?

    https://www.preprints.org/manuscript/201908.0037/v1

    Thank you Professors,
    Your pieces of advice are always useful!!!

    • August 7, 2019 4:50 am

      Sounds like a challenge! We await your github link with the source code.

      • August 7, 2019 8:07 am

        Sure!!! Why not? I will start today on GitHub with a project of Scala. I will share the link when I finish.

      • August 7, 2019 3:24 pm

        Accepted the challenge!!! Here is the github link with the reduction:

        https://github.com/frankvegadelgado/VerifyReduction

      • Pepi permalink
        August 12, 2019 6:50 am

        The proof of Theorem 9 in the paper of Frank Vega is wrong: a reduction does never keep the actual truth assignments of variables. For example if {x,y,z} are all set to True in a MONOTONE NAE 3SAT instance (which hence is not satisfied at least for this setting of variables), it is still possible to set {x, y, d_ci} to True and {z, d_ai, d_bi} to False in the corresponding MINXOR2SAT instance. And this setting leads to only one unsatisfied clause in the corresponding MINXOR2SAT P_i.

      • rjlipton permalink*
        August 12, 2019 11:13 am

        Dear Pepi:

        Many thanks. My question to Frank is: Would tests of the code discovered this issue?

        Best

        Dick

      • August 12, 2019 8:18 am

        @pepi People read these efforts. I am impressed by the dedication of the community.

      • August 12, 2019 8:46 am

        Thanks Pepi,

        When we:
        “set {x, y, d_ci} to True and {z, d_ai, d_bi} to False”
        then the statement that you proposed:
        “{x,y,z} are all set to True”
        Is actually not true because you set {x,y} to True and {z} to False.

        Everybody that reads your comment is able to detect your error: It is not necessary to read the paper for the detection of your mistake. Sorry, I cannot fix something that is not in the paper.

        Best,

        Frank

      • August 12, 2019 12:42 pm

        Dear Professor and Pepi,

        Pepi, you could email me whenever you want, asking question, doubts or finding possible flaws are welcome at anytime by email. Professor Lipton, an assertion in Scala is a pre-condition that should be validated in the instance. Every property of the instances is validated by the assertions when you run the unit test. Unfortunately, not all the proof can be covered by Boolean assertions in Scala. Therefore, I invite you to read the paper and check each Theorem with a reduction in the code into the GitHub project (you could find the right Theorem on Scala comments). The paper is not too long, either the code in GitHub project, so you might find whether the paper is correct or not in few minutes according to your experience in this field. Do not hesitate to do it and if you have any question, share it or simply email me, please.

        Thanks in advance,

        Frank

      • Pepi permalink
        August 13, 2019 1:05 am

        I am sorry, my argument was wrong, the Theorem 9 actually holds.

      • August 13, 2019 1:46 am

        @pepi, it is worthier to recognize your errors, than being right in some issue. You showed you are very honest and brave with your comments: Congrats!!! However, this does not mean my proof should be correct in all the Theorems: Do not hesitate to contact me if you see something else that I could fix it.

        Thanks in advance,

        Frank

    • Ivan Gusev permalink
      August 7, 2019 5:37 am

      Can I ask you for one simple question? Suppose there exist certain problem which is known to be in EXP, one can try to reduce the complexity of the problem changing the conditions of the output needed to get NP-complete problem from a given problem. So, if suddenly EXP problems become easier, what is the influence of the certificate? And about your paper, what your problems(ESC-2 and KEC-2) exploit in structural nature of MIN⊕2SAT and your version of 3SAT? Can you clarify it in the introduction section of your paper?

      • August 7, 2019 7:50 am

        First, it depends of the length of the certificate. If the certificate is not polynomially bounded by the input length, then this is clear evidence the problem is in NEXP or even a more difficult complexity class. Second, if the problem is EXP-complete and the given output belongs to NP-complete when the certificate is polynomially bounded by the input element, then this is clue that P is not equal to NP because we already know that P is not equal to EXP by the Heriarchy Theorem: Try to find the proof by yourself(HINT:Assume P=NP and find a contradiction). However, the results of the paper follow the other direction: I mean this might be used to show P=NP. I don’t understand the second question and what is exactly the idea I should put in the Introduction to make it better? Could you be more explicit, please? You could email me whenever you want :D. Thanks.

    • rjlipton permalink*
      August 7, 2019 7:03 am

      Dear vegafrank:

      I think you miss the point. You need to code the reduction. If you have pseudo code already then should be easy. After all you are claiming one of the great results of…

      I stand by my thought. Code it up.

      Best

      Dick

      • August 7, 2019 8:15 am

        Dear Professor,

        I will start a project on GitHub today. I think I can finish today since it is easy to transform the pseudocode to Scala or Java.

        As you suggest, maybe I could find a flaw or an improvement while I’m coding.

        Thank you for your advice.

      • August 7, 2019 3:27 pm

        Dear Professor,

        Here is the reduction of the work including the unit test. It took some hours of coding to finish the reduction algorithms.

        https://github.com/frankvegadelgado/VerifyReduction

        All the best,

        Frank

      • P. Peng permalink
        August 7, 2019 4:48 pm

        You completed the first step, now take the next one.
        Use your reduction to efficiently solve SAT problems that currently cannot be solved in any reasonable amount of time.

        Why not solve for the secret key of a large bitcoin wallet and profit?

        Or, if you don’t feel like making your own SAT problems, enter the next SAT solving competition — http://www.satcompetition.org

      • August 7, 2019 5:05 pm

        Dear Peng,

        Our reduction consists given an instance of an NP-complete problem and its certificate, then we output an element of another language in the class L. It is not a common reduction, but a verifier with output string in its tapes using a halting state instead of the acceptance or reject state. We assume the existence of such verifier is an evidence of P=NP, because we use a logspace verifier which is based the class NL and NL is a subset of P.

        Thanks

      • August 7, 2019 5:22 pm

        Important: The assumption of P=NP is not in the paper. We only explain this interesting “reduction” verifier in the paper and in the code in github we implement the verifier algorithm in Scala. Note, it has no sense to solve a SAT instance if we have already its certificate. This has only sense for a verifier.

  2. Craig permalink
    August 6, 2019 8:56 pm

    I have a psychology question: Are we humans wired to believe that P=NP? It seems to me that we are. Intellectually, I know that P is not NP (I even wrote a paper claiming to have a proof), but I cannot help feeling in my heart that they are equal. If a problem has polynomial size and its solution can be verified in polynomial time, shouldn’t it naturally follow that it can be solved in polynomial time? My intuition tells me yes, but my intellect tells me no.

    The fact that so many people claim to have proven P=NP and so many people claim to have proven they are not equal confirms to me that there is a split between the intellect and intuition with regard to this problem.

    • Ivan Gusev permalink
      August 7, 2019 4:53 am

      The answer is clear. People are not wired biologically to believe such extremely abstract ideas. Why wouldn’t you think that P can equal to NP in the finite case and not equal in the infinite case? The idea looks silly at the beginning, but if you can show that lower bounds can be lowered by restricting the maximum size of a problem you can get away with way lower bound than currently known. I do think you can even break the low and show that for certain problems it is possible to construct a polynomially-bounded algorithm that would work beneath certain N and then you can show that if N will be raised your algorithm can self-adjust itself and start to loose only certain % of instances which will be left unsolved. You can show that it can work for any finite case, the natural barrier will be easier to bypass on this ground.

      • Craig permalink
        August 7, 2019 9:09 am

        Ivan, phrase it like this: “If a problem is simple to state and its solution is simple to verify, shouldn’t it naturally follow that it can be simple to solve?”

    • rjlipton permalink*
      August 7, 2019 7:04 am

      Dear Craig:

      Interesting comment. I like your “If a problem has polynomial size and its solution can be verified in polynomial time, shouldn’t it naturally follow that it can be solved in polynomial time?” Indeed.

      Best

      Dick

      • Ivan Gusev permalink
        August 7, 2019 9:41 am

        I was thinking about the same thing for a long time trying to answer this question. And I think that I have one fundamental objection. I call it “asymmetrical property”. Sometimes some objects can’t show their properties because of the fundamental limitations of the systems they are defined within. Obviously, one can derive dozens of different models(=systems) which could show that property naturally, but it makes related math inconsistent for most of the time. I tried to bypass this weakness with L-Functions. They allow me to restate PvsNP in the realm of number theory and obtain a natural formulation of “Asymmetrical property”, which can be used to find better bounds. I can’t explain it all right now, but I’ll try to establish some actual lower bounds in the next half of the year in my first paper. I’m not sure that anyone will be interested at all, but I will try to post some papers for some time. I estimated that complete proof of P!=NP requires 300+ pages with 50+ or more serious theorems, which is not doable by non-mathematician like me. But when to stop? How can I realize that everything that I do is worthless and I’m simply deluded?

      • Craig permalink
        August 7, 2019 12:27 pm

        Magic tricks work on the basis that P != NP. Almost every magic trick has a simple stupid explanation, yet they fool people, because simple problems (how did the magician do it?) which have simple stupid solutions are not always easy to figure out. (The illusion maker Jim Steinmeyer said, “Magicians guard an empty safe.”)

        Also, laymen who are fooled by magicians usually believe that the magician is using some very complicated techniques or has incredible dexterity, because intuitively they believe that P=NP, that a problem that is difficult to solve and is easy to state (how did the magician do it?) must have a complicated solution.

      • Ivan Gusev permalink
        August 7, 2019 1:35 pm

        The answer here is simple. Mathematics wasn’t made to fool people on purpose. All of its tricks are about cleverness and clarity. Try to take a look at reversal case. FLT and others, they show that simple problems which have simple formulations can have unexpectedly large complexity

    • Jordan permalink
      August 7, 2019 5:11 pm

      As Goedel formulated this attitude, “for clear questions posed by reason, reason can also find clear answers.”

      • Craig permalink
        August 10, 2019 10:06 pm

        P!=NP can also a very depressing idea. I got into mathematics, because I thought by studying mathematicians one could eventually be able to solve any problem. But P!=NP means not only will I not be able to solve any problem, but there are problems in which the solution can be almost right in front of me and I will not even see it. So I ask what is the point of studying math?

      • rjlipton permalink*
        August 10, 2019 10:27 pm

        Dear Craig:

        Hard problems can be depressing—I agree. But we can solve many problems, and that is exciting I would say. Th point of studying math is:

        1. It is fun. 2. It is beautiful. 3. It is surprising.

        I hope you enjoy it—mean math.

        Best

        Dick

      • Craig permalink
        August 11, 2019 3:39 pm

        Dick,

        1. Math is fun, but so are games and sports.
        2. Math is beautiful, but so is art and music.
        3. Math is surprising, but so is a Hitchcock movie or a good novel.

        But one thing math is that nothing else is is it is the language of nature. You cannot understand nature without understanding math. So perhaps this is the point of studying math.

  3. August 6, 2019 11:09 pm

    If P=CH then would NC=CH or P=PSPACE be the truth? We hope truth is the latter possibility.

    • August 9, 2019 11:40 am

      No comments on this? I think NC=CH is truth.

      • August 16, 2019 11:52 pm

        It would be really nice to know where your instinct on this would be if P=CH holds true. I think it is NC=CH.

  4. August 7, 2019 4:48 am

    I agree that coding the reduction would increase our confidence in the proof. However, couldn’t there also be valid non-constructive proofs if P=NP? Or reductions that are galactic even for small cases?

    Of course I would imagine that the majority of proofs put forward are constructive and checkable for small problems, so your advice is a good filter.

    • rjlipton permalink*
      August 7, 2019 7:07 am

      Dear Spencer:

      Yes many proofs are very constructive. The reason behind the post. But of course the proof could start with: Let us pick a huge expander graph and take the product of it with this graph 100 times and…

      By thanks on the comment about it being good filter. Like that way of stating it.

      Best

      Dick

  5. P. Peng permalink
    August 7, 2019 4:37 pm

    Supplying code with a claim, even if the program works, doesn’t mean verifying the claim is easy.

    For instance, on the P vs NP wikipedia page, there is an algorithm due to Levin which solves the SUBSET-SUM problem and runs in polynomial time if and only if P=NP. Imagine if instead someone just submitted that and claimed it ran in polynomial time. How would evaluate the claim? In this case, evaluating the claim is as hard as the P vs NP problem itself.

    • August 7, 2019 7:31 pm

      P.Peng What you ask of is an unreasonable problem to confirm even if his algorithm has a reasonable run time. Provide him a problem where you really know variables remain linear in blowup and only remain in 100’s of non-deterministic bits (I find hard to find such cryptographic examples with what is known in the usual world of research and so you have to cook him an example and do a ZKP and that is likely the only way)?

  6. August 7, 2019 7:31 pm

    P.Peng What you ask of is an unreasonable problem to confirm even if his algorithm has a reasonable run time. Provide him a problem where you really know variables remain linear in blowup and only remain in 100’s of non-deterministic bits (I find hard to find such cryptographic examples with what is known in the usual world of research and so you have to cook him an example and do a ZKP and that is likely the only way)?

    • rjlipton permalink*
      August 7, 2019 9:22 pm

      Dear L:

      Not sure get your comment. I am not saying that the claimer must supply a fast run time. I am saying that coding it and even working on trivial examples would be powerful. The examples can be tiny. Thus my thesis is this:

      A mistaken claim about a reduction from SAT to say solving LP’s is wrong because it just does not work. Even for tiny examples.

      This is based on seeing many claimed proofs. It is not a theorem, of course.

      Best

      Dick

      • August 8, 2019 2:41 am

        I thought the goal is to convince the verifier of the prover’s sanity not convincing the prover of his insanity.

  7. August 8, 2019 2:41 am

    I thought the goal is to convince the verifier of the prover’s sanity not convincing the prover of his own insanity.

  8. Yuly Shipilevsky permalink
    August 8, 2019 7:21 am

    Any solution of P vs NP problem will never be published in peer-reviewed journals
    or somehow officially accepted. So it’s better to be focused on other
    problems.

    • Craig permalink
      August 8, 2019 8:42 am

      Is the goal of computer science research getting a paper published in a peer-reviewed journal or is it to understand computer science?

      • rjlipton permalink*
        August 8, 2019 11:24 am

        Dear L:

        I like the direct question. Usually the latter, insight; but the publishing pressure is strong on many.

        Best

        Dick

      • Craig permalink
        August 14, 2019 12:17 pm

        A follow up question: Nowadays, people judge scientists by how many papers and books they write – in general, the more papers and books the scientist writes, the more knowledgeable the scientist.

        But shouldn’t it be the opposite? The more papers and books the scientist reads, the more knowledgeable the scientist?

        And which is greater?

        1) The total number of science books and papers written.

        or

        2) The total number of times people besides the authors have read science books or papers.

  9. August 9, 2019 8:22 am

    Now the preprint

    https://www.preprints.org/manuscript/201908.0037/v1

    has the GitHub Repository link.

    Rephrasing Descartes:

    I prove, therefore I code!!!
    I proved, I coded and later, what else?

    • rjlipton permalink*
      August 9, 2019 10:57 am

      Dear vegafrank:

      Great to have coded. Did you run the code on examples?

      Best

      Dick

      • August 9, 2019 12:55 pm

        Dear Professor,

        I created some unit test in the project with examples. Besides, I programmed the assertion of the instances, so every time a reduction ia done, the assertions are validated. Unfortunately, my reduction requires a certificate: see more in my previous comments, the paper and the GitHub project, so you would understand the idea of my assumption and why I think it could help to solve P vs NP.

        Best,

        Frank

  10. August 12, 2019 7:28 pm

    Three journals have rejected my paper in less than two days without peer-reviewing it at all and the three ones gave similar responses, something such as: “We’re unable to consider your submission. We are sorry…”
    Nobody has not answered my two challenged comments of finding a flaw in the proof here.
    I think something smells fishy, isn’t it?

    • Craig permalink
      August 12, 2019 9:04 pm

      Vegafrank, from one P vs. NP enthusiast to another, you are playing a game with different rules than you think they are. It took me a long time to figure out the rules of the game.

      First of all, this P vs NP problem is a unique problem. If you want to convince people that they are equal, you will fail, because they are not equal. But if you want to convince people that they are not equal, you will also most likely fail because it is human psychology to not want to admit defeat, that there are easy to state problems that are difficult to solve, even if they have easy to verify solutions. My experience is that no matter what arguments one presents that P is not NP, the listener will say “maybe if you do x,y,z you will succeed and get a polynomial time algorithm”. The listener almost always thinks that he is clever enough to get around your proof by just mentioning a strategy that the proof does not mention explicitly and believing that this is enough to break the proof, even if it doesn’t break the proof.

      I have not seen much difference between trying to convince an expert in computer science that P is not NP and trying to convince an angle trisector that what he is doing is impossible.

      Most experts believe that P=NP in their hearts and do not want P not equal to NP to be true, so they will not take seriously any proof that they are unequal, even if they say they do.

      Now you might say to yourself, “but these are not angle trisectors, these are experts.”

      And I will respond, “Yes, they are experts, but they are also human beings.”

      • August 12, 2019 10:08 pm

        Craig, your point of view is very interesting!!! Thanks for sharing it!!!

      • Craig permalink
        August 12, 2019 10:28 pm

        To give an example of how difficult it is to convince experts that P is not NP, I once sent a very short paper (1 to 2 pages) to a journal with an argument that P is not NP, in which the anonymous reviewer said it was impossible that there could be such a short and simple solution to such a difficult problem.

        I responded to the editor that obviously the reviewer was prejudiced that P=NP, since only someone who believes that P=NP would say that it is impossible that there could be such a short solution to a difficult problem, as such a statement is essentially logically equivalent to P=NP.

        This irony was lost on the editor, as I recall, and the editor still rejected it.

      • August 12, 2019 10:52 pm

        It is normal that people may be suspicious of short solutions. However, this should not be taken as an argument to reject or for not considering to review. I don’t remember well, but the paper of the incompleteness theorem of Godel has few pages. This few pages changed the world for yesterday, now and so on…

  11. August 12, 2019 8:35 pm

    I mean “fishy” in a positive way: none has found a detail in the proof which support a flaw. I submitted a new version to the preprints and I changed slightly the programming code. You could view the possible new replacements here:

    https://www.preprints.org/manuscript/201908.0037

    All the best,

    Frank

  12. August 13, 2019 5:49 am

    He only claims following: ‘In this work, we show some results that might help us to solve one
    of the most important open problems in computer science’. Perhaps should be peer reviewed. Would FOCS or STOC review such paper or follow the usual procedure of garbage bin? Perhaps he should cut down all the blabber on Turing, $1million etc and submit core results. People may look at it.

    • rjlipton permalink*
      August 14, 2019 12:02 pm

      Dear L:

      I agree on decreasing the extra comments on history and millions etc. I still would like to see the code run on examples. Lost of them.

      Best

      Dick

    • August 14, 2019 3:16 pm

      Dear Professor,

      The core results are in the sections “Problems” and “Results”: they are only less than 5 pages. The result of the paper is in 4 theorems from Theorem 9 to Theorem 12. The section “Problems” covers 1 page with the definitions of all the problems of the paper. The main result is in these 4 theorems in the next remaining less than 4 pages.
      It could find the unit test with the necessary examples in:
      https://github.com/frankvegadelgado/VerifyReduction/tree/master/src/test/scala/frank/problems
      Everybody is welcome to push new examples or fixing bugs on possible pull requests on the GitHub Project. Professor Lipton, you asked for a possible code in Python, so you would need to install Python to do that. In Scala is the same, you need to install JDK 8. In addition, in my case you need to install SBT to run the unit test (you could run the unit test with “sbt test” command). I could avoid the people to install SBT, but they might not wish to see the predefined test, but add new ones and change them.

      Best,

      Frank

  13. August 16, 2019 7:36 pm

    We already know that the Theorem 9 is correct.
    What about the other theorems 10, 11 and 12?
    There is no proof without a prover and the checkers.
    Let’s see the progress on provers and checkers
    The prover:
    1-He wrote a pdf proof!
    2-He coded the proof!
    3-He provided tiny examples for testing!
    4-He convinced of a wrong claim from a possible error in the proof!
    The checkers:
    1-They asked for a code!
    2-They asked for tiny examples!
    4-They proposed the removal of extra information in the paper!
    It seems that there are 4 tasks made by a single prover and 3 whole tasks made by multiple checkers.
    Might this indicate that P vs NP has been solved?

    • August 16, 2019 11:25 pm

      Stephen Colbert will enjoy jokes.

  14. August 22, 2019 5:27 pm

    Rephrasing Galilei,

    “And yet it moves”.

    My claims of a possible proof of P vs NP, in fact, move.

    https://www.preprints.org/manuscript/201908.0037/v1

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