Sunday, March 15, 2015
Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?
When I was young and foolish and I heard that someone thinks they proven P=NP or P ≠ NP I would think Wow- maybe they did!. Then my adviser, who was on the FOCS committee, gave me a paper that claimed to resolve P vs NP! to review for FOCS. It was terrible. I got a became more skeptical.
When I was older and perhaps a byte less foolish I would think the following:
For P=NP proofs: I am sure it does not proof P=NP BUT maybe there are some nice ideas here that could be used to speed up some known algorithms in practice, or give some insights, or something. Could still be solid research (A type of research that Sheldon Cooper has disdain for, but I think is fine).
and
For P ≠ NP proofs: I am sure it does not prove P ≠ NP BUT maybe there are some nice ideas here, perhaps a `if BLAH than P ≠ NP', perhaps an nlog^* lower bound on something in some restricted model'.
Since I've joined this blog I've been emailed some proofs that claim to resolve P vs NP (I also get some proofs in Ramsey Theory, which probably saves Graham/Rothchild/Spencer some time since cranks might bother me instead of them). These proofs fall into some categories:
P ≠ NP because there are all those possibilities to look through (or papers that are far less coherent than that but that's what it comes down to)
P=NP look at my code!
P=NP here is my (incoherent) approach. For example `first look for two variables that are quasi-related' What does `quasi-related' mean? They don't say.
Papers where I can't tell what they are saying. NO they are not saying independent of ZFC, I wish they were that coherent. Some say that its the wrong question, a point which could be argued intelligently but not by those who are writing such papers.
OKAY, so is there ANY value to these papers? Sadly looking over all of the papers I've gotten on P vs NP (in my mind- I didn't save them --should I have?) the answer is an empirical NO. Why not? I'll tell you why not by way of counter-example:
Very early on, before most people know about FPT, I met Mike Fellows at a conference and he told me about the Graph Minor Theorem and Vertex Cover. It was fascinating. Did he say `I've solved P vs NP' Of course not. He knew better.
Taking Mike Sipers's Grad Theory course back in the 1980's he presented the recent result: DTIME(n) ≠ NTIME(n). Did Mike Sipser or the authors (Paul, Pippenger, Szemeredi, Trotter) claim that they had proven P vs NP? Of course not, they knew better
Think of the real advances made in theory. They are made by insiders, outsiders, people you've heard of, people you hadn't heard of before, but they were all made my people who... were pretty good and know stuff. YES, some are made by people who are not tainted by conventional thinking, but such people can still differentiate an informal argument from a proof, and they know that an alleged proof that resolves P vs NP needs to be checked quite carefully before bragging about it.
When the result that Monotone circuits have exponential lower bounds for some problems there was excitement that this may lead to a proof that P ≠ NP, however, nobody, literally nobody, claimed that these results proved P ≠ NP. They knew better.
So, roughly speaking, the people who claim they've resolved P vs NP either have a knowledge gap or can't see their own mistakes or something that makes their work unlikely to have value. One test for that is to ask if they retracted the proof once flaws have been exposed.
This is not universally true- I know of two people who claimed to have solved the problem who are pretty careful normally. I won't name names since my story might not be quite right, and because they of them retracted IMMEDIATELY after seeing the error. (When Lance proofread this post he guessed one of them,
so there just aren't that many careful people who claim to have resolved P vs NP.) And one of them got an obscure paper into an obscure journal out of their efforts.
I honestly don't know how careful Deolaikar is, nor do I know if anything of interest every came out of his work, or if has retracted it. If someone knows, please leave a comment.
I discuss Swart after the next paragraph.
I WELCOME counter-example! If you know of a claim to resolve P vs NP where the authors paper had something of value, please comment. The term of value means one of two things: there really was some theorem of interest OR there really were some ideas that were later turned into theorems (or in the case of P=NP turned into usable algorithms that worked well in practice).
One partial counter-example- Swarts claim that P=NP inspired OTHER papers that were good: Yannakakis's proof that Swart's approach could not work and some sequels that made Lance's list of best papers of the 2000's (see this post). I don't quite know how to count that.
Subscribe to:
Post Comments (Atom)
every -> ever in the title?
ReplyDeleteTheorem: P=NP iff P!=NP.
ReplyDeleteThe Kleene-Rosser paradox is a counter-example to NP-completeness.
================================================
Russell's Paradox: The set that contains all the sets that do not contain themselves. If you ask the question:"Does it contain itself?". The answer would be it contains itself iff it does not contain itself.
The Kleene-Rosser Paradox: Roughly, the function that may not be applied to itself, when combined with itself, it negates itself.
This function is a lambda expression as "k:= NOT (x x)" which reads: The meaning of k is: "x" may not be applied to "x". Then deriving "kk" results in the paradox:
kk= NOT kk
If you assume that this function is total, you derive a contradiction, then it is not total. Then, if you assume that it is not total, again, a contradiction is derived, then it is total. So, it is total iff it is not total. The Church-Rosser argument shows that this function is undefined. Here,
http://kamouna.wordpress.com/2013/08/16/all-mathematical-systems-are-inconsistent/
it has been shown as defined iff it is undefined and decidable iff it is undecidable, both on the lambda-calculus and Turing machines. Below is a proof sketch.
================================================
Step 1. Cook_Levin: For all w in L in NP,
M accepts w iff \exists A(w)=SAT.
Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
M_KR accepts w_KR iff e^-1(w_KR)= NOT e^-1(w_KR).
Step 3. Put M=M_KR and w=w_KR.
==> L.H.S. of (1) = L.H.S. of (2).
==> R.H.S. of (1) = R.H.S. of (2).
==> There is no SAT(w_KR).
==> L_KR={w_KR_i} is in NP and NOT NP-complete.
==> L_KR is a counter-example for NP-completeness.
==> SAT is (NOT) NP-complete.
==> SAT is NP-complete <==> SAT is (NOT) NP-complete,
Cook's proof is still correct despite the contradiction.
==> P=NP iff P!=NP.
================================================
best,
Rafee Kamouna.
The paradox in your arguments is that you still think that they can be correct.
DeleteSo, you believe paradox recognition is possible or impossible?
DeleteBased on your criteria, Swarts is a counter-example: "there really were some ideas that were later turned into theorems." Of course, these ideas were turned into theorem that say the converse of the initial claim, but still. The idea of looking at extended formulations is an interesting one (I admit not knowing whether Swarts was the first to propose it) and the subsequent work to prove Swarts approach wrong gave some insight on P vs NP. The main criticism that can be made against Swarts is some lack of carefulness and rigor.
ReplyDeleteP.S.: It seems that we have a very solid approach in the previous comment... or maybe not!
At the end of his paper, Cook suggests that the field of mechanical theorem proving needs badly a theoretical complexity criterion that will bring out fundamental limitations and suggest new goals to pursue. I think that such a thing also stands for questions like NP vs P. They require new mathematical and complexity tools that will change fundamentally our perception on the field.
ReplyDeleteIn most attempts to prove NP vs P their authors do not develop any such new and fundamental criterion or theorem they mostly reuse and recycle older ideas. I think this is the reason why interesting ideas are rare in these papers.
The research of Swart, Yannakakis and the papers on monotone circuits had some characteristics of innovation that is why it was interesting.
An interesting idea that I hear a lot on the study of NP-complete problems is the use of randomized algorithms and evolutionary programming for the development of more efficient algorithms. Researchers on this field still don’t claim that on these methods the will answer the big question, they only try to build faster procedures.
Let the string ww whose meaning is a paradox be an input to a Turing machine M/. It is easy to show that M accepts ww iff M does not accept \var w \bar w.
ReplyDeleteSo, forget about complexity theory since computability theory itself is contradictory.
Paradox recognition is paradoxical or not???
best,
Rafee Kamouna.
See:
ReplyDeletehttps://hal.archives-ouvertes.fr/hal-01132561
A correct proof of P=NP can never rule out another (equally correct) proof of P!=NP, and vice versa. No one seems to consider this fact even in the official Opinion Polls of 2002 and 2012.
ReplyDeleteRafee Kamouna.
This makes no sense to me whatsoever. A correct proof of P=NP would 100% rule out the possibility of a proof that P!=NP.
DeleteIt seems that they taught you that Mathematics is consistent and no one can prove its inconsistency. Learn more logic to verify what I said. All mathematicians agree with what I said.
DeleteRafee Kamouna.
Consider the correct proofs of both P=NP&P!=NP. Even so, or there exists an efficient algorithm for solving any NP-C or it doesn't exist such algorithm. This last statement cannot be also inconsistent. So the inconsistency would be in a formal system and not in the very fact of the existence of something (that by the way is not an abstract thing like a set but a more concrete thing as it is an algorithm). Furthermore the very correctness of both P=NP&P!=NP would imply that we cannot find such an efficient algorithm whatsoever. Else what would it be to have a proof of P!=NP and an example of an algorithm that solves NPC polinomially?
DeleteThat cannot be. It would imply some limit in thought (or another hole in maths perhaps.)
I've never seen a (wrong) proof of N?NP, so I don't know how they look like. But shouldn't they disclose some properties of algorithms? Or are they so indirect as to show that?
http://arxiv.org/pdf/1503.04794v1.pdf
ReplyDeleteGrand Claims by this new paper
A Polynomial Time Algorithm For
Solving Clique Problems
(And Subsequently, P=NP)
Michael LaPlante, March 9th 2015
I was hopeful but its wrong
Deletehttp://www.goodmath.org/blog/2015/04/27/a-failed-attempt-to-prove-p-np/
But he is brave i respect people like Michael LaPlante,
The Turing award announcement is supposed to go out today, according to the twitter post from OfficialACM. Yet, no announcement so far.
ReplyDeleteWant to draw more people to computer science? Make its biggest award as glamorous as the Nobel prize. (Yes, prizes should not be the motivating factor, but for better or for worse, they are the best PR tool we have).
And glamour does not just mean $1 million in prize money. It means getting your act together, and having a fixed date and time for the announcement. Like the Nobel Prize. Create hype and drama, and the glamour will follow. ACM really needs to learn from the Nobel foundation.
Dear Professor, I hope this might be a counter-example in the near future.
ReplyDeletehttps://hal.archives-ouvertes.fr/hal-01139624
and pdf in
https://hal.archives-ouvertes.fr/hal-01139624/document
Regards...
Dear Professor, I have "known better" this paper can be the solution of P versus NP:
ReplyDeletehttps://hal.archives-ouvertes.fr/hal-01139624
and pdf in
https://hal.archives-ouvertes.fr/hal-01139624/document
I hope it does...
Regards...
There's several mistakes in that paper apart from being vague in some points.
Delete1) The paper doesn't clearly define x apart from being an integer in A.
2) The definition |A| <= n^2 is redundant since it already states |A| = n. Could also define it as |A| <= n! or |A| <= 2^n and it would still be true.
3) The equation (log|A|)^k > n can be true. That equation is simply (log[n])^k > n which is true for sufficiently large k. Just plug in = 100 and k = 10.
That's just some of the several mistakes. Many so called 'proofs' of P=NP or P!=NP contain simple mistakes like those. Be more skeptical before claiming something so big. Making repeated simple mistakes like that will destroy your credibility so be careful.
Thanks Alex,
DeleteYou have misunderstood the reading:
1) Indeed, in each definition is declared x as an integer.
2) |A| is not the cardinality of the array A, but its bit-length (see definition in Theoretical Framework section). In addition, A is an array, not a set.
3) Certainly, (log|A|)^k > n is not true for some "constant" k. It seems you missed the "constant" part too. That equation is simply: it won´t exist a constant k such that (log[n])^k > n for every value of n.
Send all the possible several mistake, please. Maybe, those are similar like these ones, maybe not. Thanks for the advice.
Regards...
Indeed, in that work I proved that:
ReplyDelete$POLYLOGTIME \neq NLOGTIME$
in a trivial way. Next, I proved that:
If $P = NP$, then $POLYLOGTIME = NLOGTIME$.
in a trivial way too. From that result we can see $P \neq NP$.
For that reason I'm quite assure there are big chances that my proof were correct. Certainly, I'm truly convinced, even though I have failed several times with other intents.
Regards..
Why would anyone want to solve p=np their prize is cheap. And there are sharks,mathematicians out there ready to take away your fame.
ReplyDeleteWHAT IF P = NP?
ReplyDeleteWe define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP--complete}$ problem $\textit{SUBSET--PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET--PRODUCT}$. Moreover, we show $MAS \in \textit{NP--complete}$.
In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET--PRODUCT}$ would be in $\textit{P--complete}$, because they are $\textit{NP--complete}$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou's book is proved the following statement: ``$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input". Since $MAS$ is a succinct version of $\textit{SUBSET--PRODUCT}$ and $\textit{SUBSET--PRODUCT}$ would be in $\textit{P--complete}$, then we obtain that $MAS$ should be also in $\textit{EXP--complete}$.
Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.
You could see more on...
https://hal.archives-ouvertes.fr/hal-01233924/document
Best Regards,
Frank.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteIs P equal to NP?
ReplyDeleteWe pretend to show the answer of the P versus NP problem. We start assuming that P = NP. We prove a Theorem that states when P = NP, then the problem SUCCINCT HAMILTON PATH would be in P. But, we already know if P = NP, then EXP = NEXP. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in P, then P should be equal to EXP, because P and EXP are closed under reductions and P is a subset of EXP. However, as result of the Hierarchy Theorem the class P cannot be equal to EXP. To sum up, we obtain a contradiction under the assumption that P = NP, and thus, we can claim that P is not equal to NP as a direct consequence of applying the Reductio ad absurdum rule.
See more in
https://hal.archives-ouvertes.fr/hal-01249826
Your assertion that 'all papers which claim to solve the NP problem have no value' is in itself without proof. The least benefit of such papers is to show us a way which leads to nothing. In the mean time i agree with you that classical approaches will NEVER solve this problem either +vely or -vely. You need a new paradigm to do that. Here is a very recent publication postulating a new paradigm. You can judge yourself whether it has or hasn't any new/valuable ideas : http://arxiv.org/abs/1602.04955
ReplyDeleteLook this problem:
ReplyDeleteA succinct representation of a set of (distinct) b-bits positive integers is a Boolean circuit C with b input gates. The set represented by C, denoted S_{C}, is defined as follows: Every possible integer of S_{C} should be between 0 and (2^{b} – 1). And j is an element of S_{C} if and only if C accepts the binary representations of the b-bits integer j as input. The problem SUCCINCT MAXIMUM is now this: Given the succinct representation C of a set S_{C} and a b-bits integer x, where C is a Boolean circuit with b input gates, is x the maximum in S_{C}?
It is very easy to show this problem is not in P, because we should need n comparisons to know whether x is the maximum in a set of n (distinct) positive integers when the set is arbitrary. And this number of comparisons will be optimal. This would mean we cannot always accept every instance (C; x) of SUCCINCT MAXIMUM in polynomial-time, because we must use at least n = |S_{C}| comparisons for infinite amount of cases, where |S_{C}| is the cardinality of S_{C}. However, n could be exponentially more large than the size of (C; x).
But, at the same time, it is so easy to show this problem is in coNP. Certainly, given a b-bits integer y, we can check whether C accepts the binary representation of y (which means that y is an element of S_{C}) and x < y in polynomial-time, and thus, we could verify whether (C; x) is a "no" instance SUCCINCT MAXIMUM in polynomial-time.
However, the existence of a problem in coNP and not in P is sufficient to show that P is not equal to NP, because if P would be equal to NP, then P = coNP.
Basically is this, but you could see more in
https://hal.archives-ouvertes.fr/hal-01281254/document