[deleted]
The polynomial algorithm for 3-SAT problem (or P=NP)
21–30 of 156 posts
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#22Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)
And as always, we'd better hope that the proof is wrong. P=NP would (almost) imply the impossibility of cryptography, but even more seriously a lot of brainpower from the top theoretical computer scientists (whose proofs often begin with "suppose that P != NP...") would have been wasted :)
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#23OK, I just upvoted purely for the reason of keeping it on the front page a little longer so someone more qualified has a chance to glance at this. Without any evidence and no qualification to judge myself, it seems highly unlikely.
The prior probability of it being correct is so low that we should be flagging it, not upvoting it. There's many, many false "proofs" of P=?NP out there. If I write a paper formatted in LaTeX saying that I cloned a T-Rex in my backyard, should it be upvoted so that an expert in cloning can take a look at it?
If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions (https://github.com/anjlab/sat3) on how to run it on k-SAT instances. Because of this, I believe it increases the claim's reputability; it is easier to confirm or reject his algorithm and claim.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#24Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
It looks like the paper is fairly straightforward. It purports to give a polynomial time algorithm for 3-SAT.
Interesting facts:
- It is a O(n^4m) algorithm, where n is the number of boolean variables and m is the number of disjunctions.
- It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values.
- The author claims to have implemented and tested the algorithm on reasonably sized problems, though I don't see his code posted anywhere (?). Someone else appears to have implemented it here: https://github.com/anjlab/sat3.
- The author references no prior work, just review papers on the problem itself.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#25This is easy: just put your algorithm behind a web API. When I'm solving my NP-complete problems instantaneously, for free, I'll believe you.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#26Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)
And as always, we'd better hope that the proof is wrong. P=NP would (almost) imply the impossibility of cryptography, but even more seriously a lot of brainpower from the top theoretical computer scientists (whose proofs often begin with "suppose that P != NP...") would have been wasted :)
P=NP does not imply cryptography is impossible at all.
For example, "Quantum encryption" allows you to send data and know whether you're being eavesdropped. Then, once you manage to send it without being eavesdropped, you can use what you sent as a one-time-pad safely.
You could of course regress to distributing one time pads to everyone :-)
Also, if P = NP, there are still NP hard and Exp problems that remain outside the realm of P.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#27Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
Failure can be interesting. Consider the attempt a few months ago by Deolalikar. The ensuing public discussion, which including many big names in complexity theory and at least one Fields medallist, was very enlightening. This particular attempt involves someone claiming P=NP, and they have code. Even people who aren't complexity theorists can jump in on this one, by analyzing the code to verify it really is in P, an…
at least one Fields medallist
I think both Gowers and Tao talked about it. I don’t remember in how much depth.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#28Zero other (english) publications by the author in the Cornell archive and only four references within. Not an indicator as to whether the paper is correct (I haven't read it), but that's "smelly".
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#29I know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm ( https://github.com/anjlab/sat3 ) make this claim easier to verify than the claim P!=NP. Isn't the point that P=NP has great practical significance that will be immediately recognized?
If P=NP there might still be no practical implications - if there is a minimum complexity bound on the order of the polynomial, then it might remain completely impractical to solve np complete problems.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#30Earlier quoted context omitted.
The prior probability of it being correct is so low that we should be flagging it, not upvoting it. There's many, many false "proofs" of P=?NP out there. If I write a paper formatted in LaTeX saying that I cloned a T-Rex in my backyard, should it be upvoted so that an expert in cloning can take a look at it?
If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions ( https://github.com/anjlab/sat3 ) on how to run it on k-SAT instances. Because of this, I believe it increases the claim's reputability; it is easier to confirm or reject his algorithm and claim.
First, it doesn't appear to be independent as the author on the blog says he/we prepared it.
Second, doesn't mean much. It's almost as likely there's a bug in the code as in a proof. The only advantage is you can run some tets on it, but if it's wrong the tests may actually give you a false sense of security.
Lastly, if you prove P=NP you submit to FOCS or STOC. Let them review it.
Otherwise its just another Archimedes Plutonium.