Skip to content

P<NP

June 16, 2020


Some thoughts on P versus NP

Norbert Blum is a computer science theorist at the University of Bonn, Germany. He has made important contributions to theory over his career. Another claim to fame is he was a student of Kurt Mehlhorn, indeed the third of Mehlhorn’s eighty-eight listed students.

Today I wish to discuss a new paper by Blum.

No, it does not solve the P versus NP problem. The title of his paper is: On the Approximation Method and the P versus NP Problem. Its is available here.

Blum. like most complexity theorists, believes that P is weaker than NP. This is usually stated as P{\neq}NP. The staff at GLL have the idea that we should state this as

\displaystyle  P < NP.

This is clearer, more to the point, and logically what P{\neq}NP actually says. We will soon have T-shirts, mugs, and other stuff available in our web store at https:donotgotothisaddressplease.com.

Three Years Ago

In 2017 Blum released a paper that tried to prove P{<}NP. It caused a sensation—it was discussed on the complexity blogs such as In theory and Shtetl-Optimized. And also at GLL. Blum’s paper got thousands of Twitter mentions. Unfortunately he had to retract it, since it is wrong: He said:

The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage

Look at here for more comments that were made after his paper was released.

He did, months later in 2017, post a two-page retraction
here. His original paper’s abstract:

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev’s function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.

This approach is what we will discuss.

Today

Blum’s new paper does not claim to prove P{<}NP, but gives his thoughts on P{<}NP. I think he has earned our attention. It must have been difficult to go from thinking you have solved the problem to retracting your paper. I have thought, privately, that I had solved some neat problems. Only later to discover that I was wrong. I cannot imagine how tough it was to do this in public.

The Idea

Blum’s work on proving lower bounds began with his dissertation under Mehlhorn, which included a 1985 paper on monotone network complexity for convolutions. Earlier in 1984 Blum proved a lower bound of order {3n}. This stood for thirty years until in 2015 Magnus Find, Alexander Golovnev, Edward Hirsch, and Alexander Kulikov improved it to order {3.011n}. A long way from super-polynomial lower bounds. See also a talk about this work.

Blum’s new paper discusses an old approach to prove boolean circuit lower bounds. The methods he used in 1984 and those improved in 2015 do not seem to be on track to prove even non-linear circuit lower bounds.

Let’s look at his comments at a high level. See his paper for details.

Suppose that one has a boolean function {f(x)} that is monotone: recall this means that if {f(x)=1}, then changing some input {x_{k}} from {0 \rightarrow 1} does not change the value of {f(x)}. Then it is always possible to compute {f(x)} without using any negations: only and/or operations are needed. Sometimes one can prove that the number of such operations is super-linear, sometimes even super-polynomial. Even bounds in this restricted model can be deep.

The idea that has tempted Blum and many other complexity theorists is: Can we extend the proofs for lower bounds without negations to ones with negations? One problem is there is a function {f(x)} so that the following are true:

  1. The function is monotone;

  2. The function can be computed in polynomial time;

  3. Any monotone circuit for computing the function requires exponential size

This is the famous Tardos function due to Éva Tardos. The existence of this function sunk Blum’s original paper. And it makes life hard for this general program—this is an instance of what our previous post meant by a proof attempt running up against a fundamental law. Negations can help tremendously in computing a function.

Blum’s Paper

In his new paper he surveys boolean complexity ideas—especially those linked to monotone complexity. He begins by trying to argue that the largeness feature of the natural proofs barrier, which applies to combinatorial properties defined via sub-additive circuit complexity measures, does not constrain approximation complexity measures of the kind he envisions. He then proceeds to define CNF-DNF approximators and further what he calls sunflower approximators. He does enough development to highlight a missing piece of information about monomial representations of non-approximated pieces of the Boolean function one is trying to prove hard. He concludes that without this information, his methods cannot even prove super-linear size lower bounds on general circuits.

He ends with this assessment:

How to proceed the work with respect to the P versus NP problem? Currently, I am convinced that we are far away to prove a super-polynomial lower bound for the non-monotone complexity of any explicit Boolean function. On the other hand, the strongest barrier towards proving P{<}NP could be that it holds P = NP. To ensure that the whole time spent for working on the P versus NP problem is not used to prove an impossible theorem, I would switch to the try to develop a polynomial algorithm for the solution of an NP-complete problem.

Note, we have changed his P{\neq}NP to P{<}NP. Ken and I agree with him on trying to work both on P{<}NP and P=NP. However, see our comments below.

Open Problems

I applaud Blum for thinking about P{<}NP. We need people to be fearless if it is ever going to be solved. However, I personally believe that his approach may be wrong:

{\bullet } I am not as sure as he is that P{<}NP. I do think that P=NP is possible, especially if algorithms are allowed to be galactic. Recall these are algorithms that run in polynomial time, but in polynomials of astronomical degree.

{\bullet } Also I am not sure if the boolean approach to P{<}NP is the right one. Suppose there is a {C} so that SAT has boolean circuits of size {n^{C}} where

\displaystyle  C = 2^{2^{2^{10000}}}.

It still could be the case that P{<}NP, since there may be no uniform algorithm for SAT.

Restating the last point: I believe we should try to prove what is needed, and not any more. The approach to P{<}NP based on boolean circuit complexity is trying to prove too much. A proof that SAT has super-polynomial circuits does imply more than P{<}NP. A proof that SAT cannot be solved in time o(n\log n) on a multitape Turing machine would imply much less than P < NP, yet still be a breakthrough

Be cheap, prove the least possible.

28 Comments leave one →
  1. Geoffrey Irving permalink
    June 16, 2020 3:56 pm

    Shouldn’t it be P << NP? 🙂

  2. Pascal Koiran permalink
    June 17, 2020 12:56 am

    If you believe that P=NP but can’t prove it, try instead to prove that NP<EXP.

  3. kodlu permalink
    June 17, 2020 2:33 am

    surely in 2017Blum tried to prove P=/=NP, not P<NP.

  4. The Hacker permalink
    June 17, 2020 5:31 am

    Why don’t we focus instead of finding new algorithms for SAT (i.e. exp.), and from there we try to derive a poly. one?

    • rjlipton permalink*
      June 17, 2020 8:44 am

      Dear The Hacker:

      I like this idea. People have worked on better algorithms for SAT. But I wonder if they have thought much about galactic algorithms.

      Best and be safe

      Dick

  5. June 17, 2020 7:54 am

    Instead of boolean circuit complexity I would look at logical graph complexity, where those logical graphs are constructed from minimal negation operators.

  6. Norbert Blum permalink
    June 17, 2020 8:35 am

    I am not sure that P < NP. Over the years, sometimes I tried to prove P < NP sometimes P = NP. This is unknown since usually, I have found my mistakes myself. In 2004 I have tried to develop a polynomial algorithm for the minimum maximal matching problem in bipartite graphs of maximum degree three. This resticted problem is also NP-complete. My approach was as described in my last paper. I have a characterization theorem for a minimum maximal matching but at that time, I was not able to develop a polynomial time algorithm for the resulting improvement step. Now, I try this approach again. I am convinced that if P = NP then there is a practical algorithm for an NP-complete problem.

    • rjlipton permalink*
      June 17, 2020 8:47 am

      Dear Norbert:

      Thanks for your comment. I think your thought that if P=NP it would be a practical algorithm. Hmmm interesting intuition. Thanks again.

      Best and be safe

      Dick

    • June 20, 2020 5:40 pm

      Norbert, look at my attemption:

      https://vixra.org/abs/1809.0204

    • javaid aslam permalink
      June 27, 2020 4:31 am

      Norbert- And what would be your criteria for an algorithm to be “practical”. Would you call an algorithm with O(n^20) time complexity as practical?

  7. June 17, 2020 11:54 am

    Dear Dick,

    I don’t know how widely understood it is, but physics once had a frame problem (complexity of dynamic updating) long before AI did, but physics learned to reduce complexity through the use of differential equations and group symmetries (combined in Lie groups). One of the promising features of minimal negation operators is their relationship to differential operators. So I’ve been looking into that. Here’s a link, a bit in medias res, but what I’ve got for now.

    Differential Logic • Cactus Language

    Regards,

    Jon

  8. Abdulbasit Muhammed Taysir permalink
    June 19, 2020 3:28 am

    I personally don’t think P<NP.
    I recently discovered that it might be possible that P=NP.
    I realized that the real problems was to prove that NP-complete problems could be solved in polynomial time. I then tried to reason with one of the NP-complete problems I could get my head around, the Travelling Salesman Problem (TSP). I created an algorithm which I called the Angle-Sort algorithm. It did prove to be efficient in every scenerio that I tried where n≤5 but ≥2. Of course, I could not go further than 5 because I was using my head to get around the algorithm I developed and not a computer. For example, if n were 6, x will be 360 and I will have 360 different possibilities to try to keep track of without making a mistake.
    100% of the time I tried my algorithm, it did work. I tried to put it in a book titled "Man's Shortest Path Unveiled: A solution to the Travelling Salesman Problem". I haven't fully published it yet but I can give it to you. I think if one of the NP-complete problems could be solved, then some derivatives of the algorithm could be to used solve other NP-complete problems, thus proving that P=NP.
    I tried to tell some popular mathematicians but I never got any feedback. I guess no one listens to a 16 year old teenager who's a high school graduate in a stupid African country
    You can ask me on twitter for more @Muhd_taysir

  9. Abdulbasit Muhammed Taysir permalink
    June 19, 2020 3:33 am

    I hope you see this…

  10. javaid aslam permalink
    June 20, 2020 3:36 am

    I think it is high time to think about our “meta approach” in enabling/ignoring other’s attempts. That is, there should be more effort spent on validating somebody’s attempt/proof of the solution.
    Otherwise we might be guilty of this
    Insanity: doing the same thing over and over again and expecting different results. [Einstein]

    • Abdulbasit Muhammed Taysir permalink
      June 20, 2020 3:56 am

      Agreed…
      I even predicted a solution a few months ago but when I tried to contact some of the popular mathematicians I know, none of them gave me a feedback

  11. June 20, 2020 5:37 pm

    I found recently the following paper:

    https://www.aimsciences.org/article/doi/10.3934/naco.2018001

  12. javaid aslam permalink
    June 27, 2020 4:07 am

    Has anyone noticed–
    The site P vs. NP Page (https://www.win.tue.nl/~gwoegi/P-versus-NP.htm) is SILENT for the last 4 years!!

  13. June 27, 2020 4:20 pm

    Hi!!!

    I have found a beautiful proof about P vs NP. It is so simple and elegant that its existence seems like accident, but this does exist:

    https://doi.org/10.5281/zenodo.3355776

    I have found a way to count the number of unsatisfied clauses between all the truth assignments from a Boolean formula in 2CNF. Indeed, we show this problem is in #L and we know that #L is contained in FP. At the same time, we reduce #MONOTONE 2UNSAT to this problem, where we know that #MONOTONE 2UNSAT is #P-complete.

    I hope to hear some comments about it, please…(you can email me!!!)
    Thanks in advance,
    Frank

  14. June 29, 2020 5:56 am

    Following one piece of advice!!! Here is a short statement:

    I saw that the number of unsatisfying truth assignments in a Boolean formula \phi in 2CNF is equal to the number of unsatisfying truth assignments when a clause c_0 in \phi is unsatisfied plus the number of unsatisfying truth assignment when the same clause c_0 in \phi is satisfied.

    I also noted, if we can count the number of unsatisfied clauses between all the truth assignments for the formula \phi, then we can count the number of unsatisfying truth assignments when a clause c_0 in \phi is unsatisfied. This is simple, since we can subtract the number of unsatisfied clauses between all the truth assignments for the formula \phi with the clause c_0 and the number of unsatisfied clauses between all the truth assignments for the formula \phi without the clause c_0.

    Certainly, for some truth assignment in the formula \phi, the subtraction of the number of unsatisfied clauses in \phi when the clause c_0 is unsatisfied and the number of unsatisfied clauses in \phi without the clause c for the same truth assignment is equal to 1. Moreover, for some truth assignment in the formula \phi, the subtraction of the number of unsatisfied clauses in \phi when the clause c_0 is satisfied and the number of unsatisfied clauses in \phi without the clause c_0 for the same truth assignment is equal to 0. In this way, with this subtraction, we count only once every unsatisfying truth assignment when a clause c_0 in \phi is unsatisfied.

    In addition, we can count the number of unsatisfying truth assignments in \phi when the clause c_0 is satisfied. This will be equal to the sum of the number of unsatisfying truth assignments in “\phi* and c_i” for 1 <= i <= 3 when exactly one of the clauses c_1, c_2 or c_3 is unsatisfied, where \phi* is the formula \phi without the clause c_0 = (x or y) and the values of c1, c2 and c3 are equal to (not x or y), (x or not y) and (not x or not y), respectively. Actually, c_0 is satisfied for some truth assignment if and only if exactly one of the clauses c_1, c_2 and c_3 is unsatisfied for the same truth assignment.

    In this way, we can count the number of unsatisfying truth assignment in a Boolean formula \phi in 2CNF as the sum of the number of unsatisfying truth assignments in "\phi* and c_i" for 0 <= i <= 3 when exactly one of the clauses c_0, c_1, c_2, or c_3 is unsatisfied, where we know how to calculate them using the number of unsatisfied clauses between all the truth assignments for the formulas "\phi* and c_i" and \phi*.

    Furthermore, we achieve to count the number of unsatisfied clauses between all the truth assignments for a formula \phi in 2CNF, because that would be equal to the number of accepting paths of a nondeterministic log-space machine, where we know that #L is contained in FP. In addition, we know that #2UNSAT is #P-complete. In this way, we show a problem in #P-complete and FP and thus, P = NP. See more in:

    https://doi.org/10.5281/zenodo.3355776

    Thanks in advance,
    Frank

  15. July 4, 2020 4:52 am

    Following some good pieces of advice, then I have obtain the following result:

    P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US 1,000,000 prize for the first correct solution. We consider the following problem: Given a 2CNF formula and a natural number k, is it possible to remove at most k clauses so that the resulting 2CNF formula is satisfiable? This problem is NP-complete. We prove this problem can always be solved in polynomial time. In this way, we demonstrate the complexity class P is equal to NP.

    See more in:

    https://doi.org/10.5281/zenodo.3355776

    Thank you very much,
    Frank

  16. Serge permalink
    July 7, 2020 9:37 am

    Maybe P=NP holds, but any brain that proved it would collapse to a black hole…

  17. July 8, 2020 6:54 am

    $P$ versus $NP$ is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is $P$ equal to $NP$? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the $P$ versus $NP$ problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US 1,000,000 prize for the first correct solution. A major complexity class is $\textit{NP–complete}$, where $3SAT$ is a well-known $\textit{NP–complete}$ problem. Given a set $I$ of Boolean formulas in $3CNF$ of $n$ variables and $m$ clauses, the $NP$-optimization problem $\textit{SELECTOR–3SAT}$ consists in selecting the formula with more satisfying truth assignments, where every clause from the formulas in $I$ can be unsatisfied for some truth assignment. We prove there is an exact polynomial time algorithm for $\textit{SELECTOR–3SAT}$. As result, we obtain that the complexity class $P$ is equal to $NP$.

    See more in:

    https://doi.org/10.5281/zenodo.3355776

  18. July 24, 2020 8:44 am

    Check out a Review on my Research in P Vs NP
    https://bit.ly/3hy1qOy

  19. July 24, 2020 8:50 am

    Based on my research, I think plausibly, P = NP
    Seriously. My research only focused on one of the NP-complete problems, the Travelling Salesman problem (TSP). Proving that an NP-complete problem could be solved in polynomial time was my aim since the question P Vs NP? really is asking if NP-complete problems could be solved in polynomial time. After a lot of testing, I did came up with an algorithm. Check out my review 👉👉👉

  20. July 24, 2020 8:53 am

    Based on my research, I think plausibly, P = NP
    Seriously. My research only focused on one of the NP-complete problems, the Travelling Salesman problem (TSP). Proving that an NP-complete problem could be solved in polynomial time was my aim since the question P Vs NP? really is asking if NP-complete problems could be solved in polynomial time. After a lot of testing, I did came up with an algorithm. Check out my review 👉👉👉 https://bit.ly/3hy1qOy

  21. July 24, 2020 8:54 am

    Based on my research, I think plausibly, P = NP
    Seriously. My research only focused on one of the NP-complete problems, the Travelling Salesman problem (TSP). Proving that an NP-complete problem could be solved in polynomial time was my aim since the question P Vs NP? really is asking if NP-complete problems could be solved in polynomial time. After a lot of testing, I did came up with an algorithm. Check out my review of interested 👉👉👉 https://bit.ly/3hy1qOy

Trackbacks

  1. Differential Logic • Discussion 3 | Inquiry Into Inquiry

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