Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The polynomial algorithm for 3-SAT problem (or P=NP)

romvf.wordpress.com

Post reply on HN
Print view View original

31–40 of 156 posts

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#31

Post by [deleted] »

cyrus_ wrote: post #24
jey wrote: post #2

Why 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…

[deleted]

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#32

Post by socketpuppet »

ot wrote: post #22
chucknthem wrote: post #7

Just 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 :)

How so?

1) One time pads are provably secure albeit impractical

2) Integer factorization is BQP, but not necessarily NP-complete.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#35

Post by sonoffett »

kenjackson wrote: post #30
sonoffett wrote: post #23

Earlier quoted context omitted.

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 Archimed…

Perhaps you're right regarding the first point, I'm just going off what he states in the OP: "Also two independent versions of the algorithm in programming languages have been implemented."

My point is that a constructivist proof that P=NP along with working code (again I'm assuming it's implemented correctly, as it appears vetted by Romanov) is easier to prove incorrect as it's easier for someone who perhaps doesn't have the theoretical background to find pathological examples where it breaks down (and a much wider audience fits in this category, including most of HN).

I agree with your point about the false sense of security however--an inability to find such pathological cases is not sufficient to prove P=NP. In order to truly verify the claim a rigorous analysis of the proof will be necessary--but in this situation it's much easier to show what this guy is saying is false than in the Deolalikar case.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#37

Post by flatline »

equark wrote: post #18

I 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?

It certainly would make it easier for a professional programmer to verify, hence it has a certain appeal to this audience. Probably not so much for a mathematician.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#38

Post by tanis »

I've read the paper fairly closely, and it mostly seems like the author is hiding a conflict-driven search in ill-stated data structures, which allow him to perform a faulty analysis of the runtime of his algorithm.

I've implemented a SAT solver and read the literature extensively. This paper is not up the standards of clarity imposed by that literature, see, eg, "Efficient Conflict Driven Learning in a Boolean Satisfiability Solver" (Zhang, available for free online). There is a world of difference in the clarity of presentation between these two papers. There might be an English language barrier problem operating, I don't know.

If the author did some work to polish his presentation and state definitions more clearly, as well as submit his SAT solver to well know competitions, (http://www.satcompetition.org/2011/), I'm sure he could get some attention from the relevant people. Given how clear it looks right now, I'm too busy with my own research to try and pull out the hidden conflict-driven algorithm that I suspect exists in this paper, as it would be very time-consuming for little expected gain on my end.

If his algorithm beats the pants off all the others in SAT 2011, well, then I'd get right down to work.

Homework for someone who has some time: download his code and make it run on SAT 2010. Compare to other algorithms from that competition. Not, of course, a definitive test, but it it performs even in the middle of the pack, then you'll know it is worth a closer look.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#39

Post by ot »

socketpuppet wrote: post #32
ot wrote: post #22

Earlier quoted context omitted.

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 :)

How so? 1) One time pads are provably secure albeit impractical 2) Integer factorization is BQP, but not necessarily NP-complete.

1) One time pads require a secure channel to transmit the key, which must be the same length of the message. It is not a feasible cryptography scheme, more of a theoretical framework.

2) Integer factorization is trivially in NP (the decision problem "n has a factor < x" has a certificate: the factor)

Post reply on HN