tag:blogger.com,1999:blog-3722233.post7329933002808223925..comments2021-02-28T13:36:16.682-06:00Comments on Computational Complexity: Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-3722233.post-34467331289378165402016-03-04T08:25:36.398-06:002016-03-04T08:25:36.398-06:00Look this problem:
A succinct representation of a...Look this problem:<br /><br />A 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}?<br /><br />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).<br /><br />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.<br /><br />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.<br /><br />Basically is this, but you could see more in<br /><br />https://hal.archives-ouvertes.fr/hal-01281254/documentFrankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76465606129519622502016-02-26T09:06:36.799-06:002016-02-26T09:06:36.799-06:00Your assertion that 'all papers which claim to...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 naserhttps://www.blogger.com/profile/08349551780038577418noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13619136219446190812016-01-06T13:50:38.032-06:002016-01-06T13:50:38.032-06:00Is P equal to NP?
We pretend to show the answer o...Is P equal to NP?<br /><br />We 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.<br /><br />See more in<br /><br />https://hal.archives-ouvertes.fr/hal-01249826Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41644780807283431142015-12-24T14:54:54.665-06:002015-12-24T14:54:54.665-06:00This comment has been removed by the author.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34063326300305563672015-12-18T15:11:37.361-06:002015-12-18T15:11:37.361-06:00This comment has been removed by the author.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72107056319586211622015-12-08T15:24:56.106-06:002015-12-08T15:24:56.106-06:00This comment has been removed by the author.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8719140595418715332015-12-01T15:06:45.897-06:002015-12-01T15:06:45.897-06:00WHAT IF P = NP?
We define an interesting problem ...WHAT IF P = NP?<br /><br />We 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}$.<br /><br />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}$.<br /><br />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.<br /><br />You could see more on...<br /><br />https://hal.archives-ouvertes.fr/hal-01233924/document<br /><br />Best Regards,<br />Frank.Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71201269237171440232015-10-18T07:11:13.494-05:002015-10-18T07:11:13.494-05:00I was hopeful but its wrong
http://www.goodmath.or...I was hopeful but its wrong<br />http://www.goodmath.org/blog/2015/04/27/a-failed-attempt-to-prove-p-np/<br /><br />But he is brave i respect people like Michael LaPlante,coders lifehttps://www.blogger.com/profile/09254781425510673328noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7542919164519266002015-10-18T06:40:22.223-05:002015-10-18T06:40:22.223-05:00Why would anyone want to solve p=np their prize is...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. coders lifehttps://www.blogger.com/profile/09254781425510673328noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89931193237369829972015-05-21T18:29:07.884-05:002015-05-21T18:29:07.884-05:00Consider the correct proofs of both P=NP&P!=N...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?<br />That cannot be. It would imply some limit in thought (or another hole in maths perhaps.)<br />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?nachhhhttps://www.blogger.com/profile/10492335752915616695noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25933707536161241812015-04-10T15:16:01.956-05:002015-04-10T15:16:01.956-05:00Thanks Alex,
You have misunderstood the reading:
...Thanks Alex,<br /><br />You have misunderstood the reading:<br /><br />1) Indeed, in each definition is declared x as an integer.<br /><br />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.<br /><br />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.<br /><br />Send all the possible several mistake, please. Maybe, those are similar like these ones, maybe not. Thanks for the advice.<br /><br />Regards...<br />Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43170907505110301482015-04-09T20:09:02.377-05:002015-04-09T20:09:02.377-05:00There's several mistakes in that paper apart f...There's several mistakes in that paper apart from being vague in some points. <br /><br />1) The paper doesn't clearly define x apart from being an integer in A. <br /><br />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. <br /><br />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.<br /><br />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.Anonymoushttps://www.blogger.com/profile/02541169310011752012noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22964158162731759662015-04-08T13:41:02.269-05:002015-04-08T13:41:02.269-05:00Indeed, in that work I proved that:
$POLYLOGTIME ...Indeed, in that work I proved that:<br /><br />$POLYLOGTIME \neq NLOGTIME$<br /><br />in a trivial way. Next, I proved that:<br /><br />If $P = NP$, then $POLYLOGTIME = NLOGTIME$.<br /><br />in a trivial way too. From that result we can see $P \neq NP$.<br /><br />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.<br /><br />Regards..Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66869507151203149482015-04-07T09:48:17.430-05:002015-04-07T09:48:17.430-05:00Dear Professor, I have "known better" th...Dear Professor, I have "known better" this paper can be the solution of P versus NP:<br /><br />https://hal.archives-ouvertes.fr/hal-01139624<br /><br /><br />and pdf in <br /><br />https://hal.archives-ouvertes.fr/hal-01139624/document<br /><br />I hope it does...<br /><br />Regards...Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66812311194502078872015-04-07T09:40:27.266-05:002015-04-07T09:40:27.266-05:00Dear Professor, I hope this might be a counter-exa...Dear Professor, I hope this might be a counter-example in the near future.<br /><br />https://hal.archives-ouvertes.fr/hal-01139624<br /><br /><br />and pdf in <br /><br />https://hal.archives-ouvertes.fr/hal-01139624/document<br /><br />Regards...Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75950119355120726792015-03-17T23:21:47.775-05:002015-03-17T23:21:47.775-05:00It seems that they taught you that Mathematics is ...It 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.<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87104368260150705862015-03-17T18:40:44.371-05:002015-03-17T18:40:44.371-05:00This makes no sense to me whatsoever. A correct p...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. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63956839689121978192015-03-17T12:14:53.349-05:002015-03-17T12:14:53.349-05:00The Turing award announcement is supposed to go ou...The Turing award announcement is supposed to go out today, according to the twitter post from OfficialACM. Yet, no announcement so far.<br /><br />Want 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). <br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38560908350063251922015-03-17T12:06:09.500-05:002015-03-17T12:06:09.500-05:00http://arxiv.org/pdf/1503.04794v1.pdf
Grand Claims...http://arxiv.org/pdf/1503.04794v1.pdf<br />Grand Claims by this new paper<br />A Polynomial Time Algorithm For<br />Solving Clique Problems<br />(And Subsequently, P=NP)<br />Michael LaPlante, March 9th 2015 Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33269329343952269152015-03-17T11:08:50.373-05:002015-03-17T11:08:50.373-05:00A correct proof of P=NP can never rule out another...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.<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58171067548550038142015-03-17T10:22:41.380-05:002015-03-17T10:22:41.380-05:00See:
https://hal.archives-ouvertes.fr/hal-0113256...See:<br /><br />https://hal.archives-ouvertes.fr/hal-01132561Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71514967774156250742015-03-16T23:21:38.873-05:002015-03-16T23:21:38.873-05:00Let the string ww whose meaning is a paradox be an...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.<br /><br />So, forget about complexity theory since computability theory itself is contradictory.<br /><br />Paradox recognition is paradoxical or not???<br /><br />best,<br /><br />Rafee Kamouna. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39488666586820021512015-03-16T15:36:28.466-05:002015-03-16T15:36:28.466-05:00At the end of his paper, Cook suggests that the fi...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.<br />In 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.<br />The research of Swart, Yannakakis and the papers on monotone circuits had some characteristics of innovation that is why it was interesting.<br />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.Pantelis Rodishttps://www.blogger.com/profile/11999985308984556045noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90705472354842397402015-03-16T08:17:54.545-05:002015-03-16T08:17:54.545-05:00So, you believe paradox recognition is possible or...So, you believe paradox recognition is possible or impossible?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39436404288645435442015-03-16T06:33:36.123-05:002015-03-16T06:33:36.123-05:00The paradox in your arguments is that you still th...The paradox in your arguments is that you still think that they can be correct.Anonymousnoreply@blogger.com