P<NP
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
This is clearer, more to the point, and logically what P
|
Three Years Ago
In 2017 Blum released a paper that tried to prove P
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
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 
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 
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
- The function is monotone;
- The function can be computed in polynomial time;
- 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
Open Problems
I applaud Blum for thinking about P
It still could be the case that P
Restating the last point: I believe we should try to prove what is needed, and not any more. The approach to P
Be cheap, prove the least possible.
Shouldn’t it be P << NP? 🙂
Good point! Though getting one < is quite enough… And there is the possibility of “=”.
If you believe that P=NP but can’t prove it, try instead to prove that NP<EXP.
surely in 2017Blum tried to prove P=/=NP, not P<NP.
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?
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
Instead of boolean circuit complexity I would look at logical graph complexity, where those logical graphs are constructed from minimal negation operators.
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.
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
Norbert, look at my attemption:
https://vixra.org/abs/1809.0204
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?
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
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
I hope you see this…
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]
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
I found recently the following paper:
https://www.aimsciences.org/article/doi/10.3934/naco.2018001
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!!
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
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
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
Maybe P=NP holds, but any brain that proved it would collapse to a black hole…
$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
Check out a Review on my Research in P Vs NP
https://bit.ly/3hy1qOy
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 👉👉👉
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
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