tag:blogger.com,1999:blog-3722233.post8342632870222880537..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: So You Think You Settled P verus NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-3722233.post-43531752028428191022022-02-07T13:51:24.652-06:002022-02-07T13:51:24.652-06:00That's a weird thing to be a consensus, seeing...That's a weird thing to be a consensus, seeing as NP literally stands for "nondeterministic polynomial time"---i.e. if randomness doesn't buy you super-polynomial power, then, uh, P=NP. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52939026331154835822014-03-29T18:36:34.425-05:002014-03-29T18:36:34.425-05:00I can relate with some of the people here. I have...I can relate with some of the people here. I have gone to professors with ideas that I thought were really cool, mind you, I wasn't claiming P=NP, but in the end I came out a little bit humbled and with a good amount of respect for the great patience that some professors have.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33158075224843787412013-10-10T01:33:47.942-05:002013-10-10T01:33:47.942-05:00What a negative post, the author believes/assumes ...What a negative post, the author believes/assumes that NP is not equal to P, and thus the post would is valid because proving NP is not equal to P is indeed impossible. <br />I don't think a mathematician should believe or assume anything. Only Pure Logic should be used, nothing else.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36232621540388532462010-09-29T15:26:44.977-05:002010-09-29T15:26:44.977-05:00I just did a quick read of Luigi Salami's proo...I just did a quick read of Luigi Salami's proof and I can verify that it is indeed correct. Unfortunately, he has not submitted it to my journal, so I must remain entirely anonymous. I would be very interested to see more of your work in the future.<br /><br />-RKAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24486659866559616032010-09-29T12:37:07.236-05:002010-09-29T12:37:07.236-05:00I'm at step 5).
If you see www.visainformatica...I'm at step 5).<br />If you see www.visainformatica.it/3sat (italian page, but link to english page) and you write me errors [small or large] I do not go to step 7) and to avoid passing stupid.<br />If there is someone so kind ..<br />Thanks, regards.luigi saleminoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74244712727492323792010-09-19T11:38:23.954-05:002010-09-19T11:38:23.954-05:00What if the very P≠NP question is a stupid idea?
I...What if the <i>very P≠NP question</i> is a <a href="http://www.xamuel.com/misconceptions-about-pnp/" rel="nofollow">stupid idea</a>?<br />I wouldn't be surprised, it just happened that the formulation by Stephen Cook was "tidy" but how is this an argument about the importance of the result?<br />Mathematicians are childishly playing with their abstruse toys without much regard for reality...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27635721402042518352010-09-18T21:19:36.363-05:002010-09-18T21:19:36.363-05:00As a practical matter, assuming your interests lie...As a practical matter, assuming your interests lie on the NP=P side of the question, it should suffice to demonstrate an algorithm which quickly solves hard instances of Satisfiability derived from polynomial reduction of factoring or theorem proving problems. While not a formal resolution of P vs NP, it is instantly self-evident whether what you have done actually works.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27656502691147909782010-08-16T15:29:13.342-05:002010-08-16T15:29:13.342-05:00@23: you have something there ...@23: you have something there ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3803622275270024412010-08-16T13:11:52.576-05:002010-08-16T13:11:52.576-05:00Seems so very apt in case of Deolalikar. But I hop...Seems so very apt in case of Deolalikar. But I hope that something can be salvaged from his attempt - if nothing else, the speed and enthusiasm of all the online collaborators should point to a new and faster way of working on promising new ideas.Vaibhavnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1485705224762798602010-07-23T12:42:53.064-05:002010-07-23T12:42:53.064-05:00Jack white says:
Lance,
"You are wrong"...Jack white says: <br />Lance,<br />"You are wrong" = "Guilty unless proven otherwise"<br />---<br />Grigori Perelman might agree.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81344756205906395412010-07-23T12:39:01.458-05:002010-07-23T12:39:01.458-05:00What about Grigori Perelman being proved correct, ...What about Grigori Perelman being proved correct, after submitting to an "online archive". Then he rejected the academic establishment ;)<br /><br />Some introspection is in order for the academic establishement, no seriously ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90346091185365616322009-12-04T05:03:55.185-06:002009-12-04T05:03:55.185-06:00Is there some sort of partial joke here? Because i...Is there some sort of partial joke here? Because it sounds like it's saying P?=NP CAN'T be resolved, as anyone who "thinks" they have a solution is "wrong" acoording to "step 1".<br /><br />Granted, there are oodles of crank "proofs" out there but that doesn't mean a real proof (for whichever is true: P=NP or P!=NP) is impossible.mike3https://www.blogger.com/profile/15516648613972933636noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9602151594356510122009-01-22T19:40:00.000-06:002009-01-22T19:40:00.000-06:00Lance,"You are wrong" = "Guilty unless proven othe...Lance,<BR/>"You are wrong" = "Guilty unless proven otherwise"Jack whitehttps://www.blogger.com/profile/07326010913365912016noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62796033142474239282009-01-22T19:36:00.000-06:002009-01-22T19:36:00.000-06:00Anon 13, {Proof: NP != P}Couple of years ago UC Be...Anon 13, {Proof: NP != P}<BR/>Couple of years ago UC Berkeley did exactly this-- they had a workshop on resolving the P vs NP issue.<BR/>But all they were discussing was a framework for proving NP != P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58715005193428387992009-01-22T19:28:00.000-06:002009-01-22T19:28:00.000-06:00Anon and Lance,To prove NP=P you don't even need t...Anon and Lance,<BR/><BR/>To prove NP=P you don't even need to worry about an NP-complete language.<BR/><BR/>How about counting all the perfect matchings? What is the NP-hard language here? (Let's not talk about the P-time reduction here)<BR/><BR/>Proving a construction (an algorithm) for one machine would be a lot easier than proving the un-computability on perhaps infinitely many machines.<BR/>The later approach is a big issue here!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15856229625405817782009-01-22T19:12:00.000-06:002009-01-22T19:12:00.000-06:00I don't think people have made much progress since...I don't think people have made much progress since Galileo.<BR/><BR/>The sheer arrogance and ignorance continue to thrive.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86637982190633154772009-01-22T18:59:00.000-06:002009-01-22T18:59:00.000-06:00Anon #14 (response to Paulina),Aren't you pre-supp...Anon #14 (response to Paulina),<BR/>Aren't you pre-supposing that an NP-complete(-hard) problem will take exponential time?<BR/>If a problem already has a polynomial time algorithm, then how do you define a super-polynomial speedup?<BR/><BR/>Another flaw in people's thinking is that they are assuming the algorithm will have to work as a SEARCH or existence solution. Counting has been assumed to be harder than search. Is there any proof of that? What if counting leads to the solution to a search problem -- in O(n^50) time?<BR/><BR/>There is just too much of belief in NP!=P, too many tacit conjectures, and that may be the biggest hurdle.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48555292562554211282009-01-16T23:46:00.000-06:002009-01-16T23:46:00.000-06:00Sorry, Last sentence:Nevertheless, a lot of time i...Sorry, Last sentence:<BR/><BR/>Nevertheless, a lot of time is needed to absorb the SHOCK, not to understand it!<BR/><BR/>Tip:<BR/><BR/>Solve the relevance of Music to P vs. NP, you will soon find out why Integer Factoring (in NP) is more difficult than SAT (NP-complete)!<BR/><BR/>It is not necessary to sing songs from Susan Haack to Lotfi Zadeh for this, yet sufficient!<BR/><BR/>Best,<BR/><BR/>Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51146863090826528852009-01-16T23:36:00.000-06:002009-01-16T23:36:00.000-06:00Anon 5:Rafee Kamouna didn't do any of the above. T...Anon 5:<BR/><BR/>Rafee Kamouna didn't do any of the above. The above steps assume a proof. I submitted nothing but a one-step argument. Run this Prolog program:<BR/><BR/>Young(John,0.7).<BR/><BR/>?- Young(John,0.7).<BR/><BR/>It will give you the answer:"Yes"="1" contradicting "0.7". There is nothing to understand here, either you agree that this is a self-contradictory fact or disagree. If you agree, then all the results follow with immediate effect. No single proof step is required. Just this one-step argument. If you disagree, then your disagreement is IDEOLOGICAL.<BR/><BR/>So, either all the results follow, or mathematics and science is an ideology and not a methodology.<BR/><BR/>Nevertheless, a lot of time is needed to absorb the SHOCK, not to understand what it!<BR/><BR/><BR/>Best,<BR/><BR/>Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4873938317674047462009-01-16T06:19:00.000-06:002009-01-16T06:19:00.000-06:00@paulina: PRIMES \in P was not surprising. The con...@paulina: PRIMES \in P was not surprising. The consensus within the community is that randomness does not buy you super-polynomial power. The primes problem had a very simple randomized algorithm that was known for a long time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84693142066782779312009-01-16T00:42:00.000-06:002009-01-16T00:42:00.000-06:00Theorem: P!=NPProof: P!=NP.You think I'm wrong? Co...Theorem: P!=NP<BR/>Proof: P!=NP.<BR/><BR/>You think I'm wrong? Come on, you have to find the flaw in my proof!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91848193199391977872009-01-15T12:49:00.000-06:002009-01-15T12:49:00.000-06:00www.timescube.com :)www.timescube.com :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16915981587222471562009-01-15T02:14:00.000-06:002009-01-15T02:14:00.000-06:00Well, eventhough there are for sure many crackpot ...Well, eventhough there are for sure many crackpot ideas put forward, I consider the academic attitude towards the P/NP issue far too biased and even presumptuous towards "P!=NP, and it simply cannot be proven". The list above just adds evidence to my view. Or is there any way to reach an "accept" state? Why isn't there? Just because the beliefs are too strong. Sure, there must be tight filters. But given the hardness of the question, and considering hardly anybody can make a living working just on this question, which is 'considered unsolvable', how would you accept a sound solution put forward by someone never heard of? Sure, todays crackpots have many options to discredit themselves, but then, is formal proof the only way for this century's Einstein to be appreciated?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57059007001559306012009-01-14T22:57:00.000-06:002009-01-14T22:57:00.000-06:00so wait a second, you are telling me that P vs NP ...so wait a second, you are telling me that P vs NP is not do-able ?<BR/><BR/>I believe that P=NP. come on,everyone, would that be such a huge surprise ? <BR/><BR/>how surprising was it when we saw that primes in p.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12565064675153099382009-01-14T21:23:00.000-06:002009-01-14T21:23:00.000-06:00Actually, private think tanks are not religious at...Actually, private think tanks are not religious at all. They don't worship God, but themselves.Anonymousnoreply@blogger.com