- You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof.
- You believe the proof is correct. Your belief is incorrect. Go back to step 1.
- Are you making any assumptions or shortcuts, even seemingly small and obvious ones? Are you using words like "clearly", "obviously", "easy to see", "should", "must" or "probably"? You are claiming to settle perhaps the most important question in all of mathematics. You don't get to make assumptions. Go back to step 1.
- Do you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time nk (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
- You submit your paper to an on-line archive. Maybe some people tell you what is missing or wrong in your paper. This should cause you to go to step 1. But instead you make a few meaningless changes to your paper and repost.
- Eventually people ignore your paper. You wonder why you aren't getting fame and fortune.
- You submit your paper to a journal.
- The paper is rejected. If you are smart you would go back to step 1. But if you were smart you would never have gotten to step 7.
- You complain to the editor that either the editor doesn't understand the proof or that it is easily fixed. You are shocked a respectable editor or journal would treat your paper this way.
- You resubmit the paper, appeal, try other journals all to no avail.
- You are convinced "the establishment" is purposely suppressing your paper because our field would get far less interesting if we settle the P versus NP problem so we have to keep it open at all costs.
- If I tell you otherwise would you believe me?
Wednesday, January 14, 2009
So You Think You Settled P verus NP
Subscribe to:
Post Comments (Atom)
looks like a post by Bill,
ReplyDeletenot lance.
Do you have any example of people going as far as step 9 (for the P=NP question) ?
ReplyDeleteI don't want any names.
I have seen a paper go to step 10. The author claimed it was the job of the referees to find an explicit counterexample to his proof, rather than his job to write a comprehensible and convincing proof.
ReplyDelete(His was the common mistake of claiming without adequate proof that any algorithm that solved his problem had to work in the way he specified.)
David Johnson
I love this policy line from JACM:
ReplyDeleteNo author may submit more than one paper on the P/NP or related long-standing questions in complexity theory in any 24 month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts.
Anon 2: Rafee Kamouna has done this and has made his name public; see, e.g., the recent exchange on Luca's blog
ReplyDeleteDo you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time nk (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
ReplyDeleteyou don't need to find an L; proving the existence of such L is sufficient.
When I was in 2nd year undergrad, someone mentioned the book "Emperor's New Mind" by Penrose, which I then read. This book introduced me to the P/NP problem and the lack of poly time algorithm for SAT.
ReplyDeleteI thought about this problem and came up with (a wrong) polytime algorithm to solve 3SAT. I coded the algorithm and tried it on a few instances and found it to work great.
Hence, I sent an e-mail to a leading professor in the field with my "findings."
He was kind enough to explain how it is unlikely that my algorithm works. He asked me to write a SAT instance generator for Pigeon Hole Principle and try the generated instance on my SAT solver.
Of course, that showed me the problems with my algorithm.
Looking back, I really appreciate the patience of this professor. He must be receiving a lot of e-mails from nuts who claim to have solved the P/NP problem.
Someone should build up this list into a game: "Chutes and Ladders, Crackpot Science Edition".
ReplyDeleteLance has provided some chutes, we just need more ladders. For starters:
'Befriend and influence a once-famous scientist who is now aged and emotionally vulnerable.'
'Receive a grant from a private think-tank which believes P=NP for religious reasons.'
'Organize an ongoing symposium for the discussion of your ideas, to meet alternate Wednesdays in the public library.'
The one thing I'm not clear on is what the victory conditions would be. Maybe the game just loops.
Actually, private think tanks are not religious at all. They don't worship God, but themselves.
ReplyDeleteso wait a second, you are telling me that P vs NP is not do-able ?
ReplyDeleteI believe that P=NP. come on,everyone, would that be such a huge surprise ?
how surprising was it when we saw that primes in p.
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?
ReplyDeletewww.timescube.com :)
ReplyDeleteTheorem: P!=NP
ReplyDeleteProof: P!=NP.
You think I'm wrong? Come on, you have to find the flaw in my proof!
@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.
ReplyDeleteThat'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.
DeleteAnon 5:
ReplyDeleteRafee 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:
Young(John,0.7).
?- Young(John,0.7).
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.
So, either all the results follow, or mathematics and science is an ideology and not a methodology.
Nevertheless, a lot of time is needed to absorb the SHOCK, not to understand what it!
Best,
Rafee Kamouna.
Sorry, Last sentence:
ReplyDeleteNevertheless, a lot of time is needed to absorb the SHOCK, not to understand it!
Tip:
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)!
It is not necessary to sing songs from Susan Haack to Lotfi Zadeh for this, yet sufficient!
Best,
Rafee Kamouna.
Anon #14 (response to Paulina),
ReplyDeleteAren't you pre-supposing that an NP-complete(-hard) problem will take exponential time?
If a problem already has a polynomial time algorithm, then how do you define a super-polynomial speedup?
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?
There is just too much of belief in NP!=P, too many tacit conjectures, and that may be the biggest hurdle.
I don't think people have made much progress since Galileo.
ReplyDeleteThe sheer arrogance and ignorance continue to thrive.
Anon and Lance,
ReplyDeleteTo prove NP=P you don't even need to worry about an NP-complete language.
How about counting all the perfect matchings? What is the NP-hard language here? (Let's not talk about the P-time reduction here)
Proving a construction (an algorithm) for one machine would be a lot easier than proving the un-computability on perhaps infinitely many machines.
The later approach is a big issue here!
Anon 13, {Proof: NP != P}
ReplyDeleteCouple of years ago UC Berkeley did exactly this-- they had a workshop on resolving the P vs NP issue.
But all they were discussing was a framework for proving NP != P.
Lance,
ReplyDelete"You are wrong" = "Guilty unless proven otherwise"
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".
ReplyDeleteGranted, 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.
What about Grigori Perelman being proved correct, after submitting to an "online archive". Then he rejected the academic establishment ;)
ReplyDeleteSome introspection is in order for the academic establishement, no seriously ...
Jack white says:
ReplyDeleteLance,
"You are wrong" = "Guilty unless proven otherwise"
---
Grigori Perelman might agree.
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.
ReplyDelete@23: you have something there ...
ReplyDeleteAs 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.
ReplyDeleteWhat if the very P≠NP question is a stupid idea?
ReplyDeleteI 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?
Mathematicians are childishly playing with their abstruse toys without much regard for reality...
I'm at step 5).
ReplyDeleteIf 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.
If there is someone so kind ..
Thanks, regards.
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.
ReplyDelete-RK
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.
ReplyDeleteI don't think a mathematician should believe or assume anything. Only Pure Logic should be used, nothing else.
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.
ReplyDelete