9 ms·
The polynomial algorithm for 3-SAT problem (or P=NP)
- jey 16y agoWhy do we think this is worthy of voting up? Is there any reason to think it might be correct?
- monochromatic 16y agoIt's on the arXive, so you know it's legit.
- jey 16y agoSarcasm, right? The arXiv has very little quality control (intentionally).
- roel_v 16y agoI think the point was that quite a bit of what is on arXiv is from quacks and nutcases. (maybe not the majority, or even a large part - but enough to cast some shadow over arXiv itself, and therefore over other submissions as well).
- zitterbewegung 16y agoJust because its on arXiv doesn't mean its legitimate. Its more likely that it is legitimate if it gets published (with a few exceptions like the Poincaré conjecture.
- deleted 16y ago[deleted]
- tzs 16y agoFailure 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, and by trying to find problem instances it fails on.
- celoyd 16y agoat least one Fields medallist I think both Gowers and Tao talked about it. I don’t remember in how much depth.
- azakai 16y agoIt is almost certainly not correct, simply because so many have tried, and none succeeded. However, this guy seems very cool - he is humble about his work, appears very serious, and even puts his code on github. And even if wrong, his approach might be interesting.
- vilda 16y ago"because so many have tried, and none succeeded" Words worth of a politician, but not a hacker!
- lwat 16y agoWe just want to know what the flaw in his reasoning is.
- cyrus_ 16y agoIt 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 https://github.com/anjlab/sat3. - The author references no prior work, just review papers on the problem itself.
- deleted 16y ago[deleted]
- wnoise 16y ago> - It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values. Any yes/no NP solver can be turned into one that does this with polynomial overhead. After finding there is a solution, you ask it the similar problem "does this have solution with the first bit set to true?", then "does this have a solution with the first bit set to <answer to previous question> and the second bit set to true?", and so forth until you've identified all bits.
- jackfoxy 16y agoOK, 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.
- jey 16y agoThe 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?
- sonoffett 16y agoIf 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 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.
- kenjackson 16y agoFirst, 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.
- sonoffett 16y agoPerhaps 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.
- phamilton 16y agoI don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"
- pedrocr 16y ago3-SAT isn't just NP, it's NP-Complete. So a solution for 3-SAT is also a solution for all other NP problems. http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-complete
- moultano 16y agoThat's incorrect unless I'm misreading you. 3 SAT is NP-complete, which means that if this algorithm's polynomial performance holds up, you can generalize it to solve any problem in NP in poly time.
- jchonphoenix 16y agoJust to be nitpicky, 3 SAT is NP-Complete which means its NP-hard. The NP-hard property allows you to reduce any problem in NP to it. As you stated it, generalizing (or reducing) 3-SAT to another problem proves nothing and is a common mistake for undergraduates learning complexity theory (reducing the wrong way).
- natep 16y agoHe said generalize it (the algorithm) to other NP problems, which I took to mean 'turn every NP problem into 3-SAT and solve that'
- jchonphoenix 16y agoThe word generalize is meaningless and undefined, which is what led to your confusion as well as multiple interpretations (which is one of the things I was picking at). To say you generalize an NP problem isn't even a statement that typechecks in the language of complexity. Reduction on the other hand, is a formally defined term and is very specific in what it means exactly.
- hc 16y agolol
- hc 16y agosorry guys. this site is not worth taking seriously anymore
- chucknthem 16y agoJust this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 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 http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)
- ot 16y agoAnd 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 :)
- Peaker 16y agoP=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.
- ot 16y agoThat's why I said "almost" :) AFAIK, cryptography without P != NP is an open question. BTW, quantum encryption is not encryption as we know it (a purely functional deterministic bijective transformation of the message), as it requires special hardware, optical fibers, etc... As of EXP etc... I am not aware of any (theoretical) encryption schemes that use problems harder than NP (actually most use circuit complexity, so NP/poly, but it is related). In designing encryption you often want polynomial verifiability (for decryption), and that implies NP membership.
- socketpuppet 16y agoHow so? 1) One time pads are provably secure albeit impractical 2) Integer factorization is BQP, but not necessarily NP-complete.
- equark 16y agoI know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm (https://github.com/anjlab/sat3 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?
- MarkPNeyer 16y agoIf 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.
- flatline 16y agoIt 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.
- jchonphoenix 16y agoYou'd be surprised. Sometimes its much harder to find hidden faulty logic in a proof for an algorithm's correctness or running time. If I recall correctly, Ramanujan once wrote a proof for 1=2 that baffled mathematicians for quite some time before they figured out what was wrong. I believe that proof was rather short (< 1 page). For a long proof with a tiny error, things could be much worse.
- spicyj 16y agoCan you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.
- chrisaycock 16y agoI was able to find this, though it's just some algebra tricks rather than a professional mathematician's musings: http://www.innovatia.com/Design_Center/Proof_that_2=1.htm http://www.innovatia.com/Design_Center/Proof_that_2=1.htm
- cperciva 16y agoI'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Being able to solve a particular problem doesn't mean that the algorithm works in general. He would have done better to demonstrate his algorithm on "known hard" problems. 3. He states a running time of O(n^4 m), but his experimental results don't scale quite like this; perhaps his analysis is wrong, or perhaps there's just a monster hiding behind the big-O. 4. If he is correct, and his algorithm is optimal, we probably don't need to worry very much about cryptography yet: It looks like this algorithm is far too slow to be a practical attack on existing cryptosystems. (EDIT: Oops, in the time it took me to write that, 18 other people posted comments. Well, so much for getting the discussion started...)
- tshaddox 16y agoTo pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to mean that). I suppose a proof that P=NP would still technically threaten cryptography, because if you assume that computer hardware performance increases polynomially with time you must concede that any given crypto technique will become practical to break after some amount of time.
- jchonphoenix 16y agoActually, yes. Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. Additionally, P=NP suggests that NP in RP. If an inefficient deterministic algorithm in P is found, I'm sure a much faster randomized algorithm would soon follow.
- deleted 16y ago[deleted]
- bdr 16y agoThis 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.
- stevejohnson 16y ago"Instantaneously, for free" is nowhere near what this paper claims (O(n^4m)).
- dangrossman 16y agoWhy would a polynomial time algorithm become instantaneous if you stick it behind an API?
- slashcom 16y agoZero 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".
- dauphin 16y agoYeah, and, seriously, a Russian?! Please...
- mitko 16y agoWhy not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants. Edit: why downvoting?
- spicyj 16y agoI interpreted dauphin's comment as sarcasm.
- dauphin 16y agoJa, I don't like when some people refer to other people saying he "smells", that's gross. And in this case, it's also plainly false: Russians don't smell more than, say, redheads.
- dauphin 16y ago> Edit: why downvoting? Please stop, you do understand.
- ezalor 16y agoPerfume was illegal in USSR until 1986.
- vilda 16y agoNot really. There are many great researchers publishing in their language only. Especially in countries where research is not heavily funded. For some, 800EUR for a conference is just too much.
- gus_massa 16y agoI don't understand something in the blog post. What did they proved in 2002 and what is the new result that they proved now?
- tanis 16y agoI'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/ 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.
- xtacy 16y agoI would like to clarify that just because an algorithm runs slower than the ones used by solvers in competitions like SAT, it doesn't mean much, as we're looking at asymptotic complexity here. To give an example: the "PRIMES is in P" paper gives a poly time algorithm to determine if a given number is prime or not, but in practice, it runs slower than tests like probabilistic algorithms like Miller-Rabin.
- tanis 16y agoVery true, I'm sorry if I implied otherwise above. However, using a well-known SAT benchmark to assess correctness/performance in the absence of a clearer statement of the algorithm would still be a good step to take, if someone was interested.
- 16y ago
- ezalor 16y agoGuess it's time to switch my SSH key to 4096 bits ECDSA. Good bye RSA.
- leelin 16y agoWhere is the market among the HN community on betting this proof is correct (or the market for P=NP in general)? My bid/ask is 0% / 0.02% I think I'd wager at most a 1% chance that P = NP, and, I'll be generous and put the odds that this particular person cracked it first at 2% of 1% (I know he has code posted, but think of all the smart people who failed, and within my 1% is the case where P=NP but no human ever proves it). Would anyone offer better odds than 1 in 5,000, or make a bid? My knowledge is limited to taking Sipser's intro class in school; but as a programmer, I always find subset-sum to be the most tangible and convincing example that NP-hard feels pretty tough. I love these announcements though; I am always humbled and fascinated by the resulting discussion.
- caf 16y agoI believe Intrade are open to suggestions for new markets (they have "Scientific" category where this would fit).
- bravura 16y agohttp://www.longbets.org/ http://www.longbets.org/ is a market for long bets, e.g. “Over a ten-year period commencing on January 1, 2008, and ending on December 31, 2017, the S & P 500 will outperform a portfolio of funds of hedge funds, when performance is measured on a basis net of fees, costs and expenses.” PREDICTOR: Warren Buffett CHALLENGER: Protege Partners, LLC
- khafra 16y agoCosts $50 to publish a bet there, though, so transaction costs would eat up anything but a very, very large bet at 0.2%
- eru 16y agoI'd put some money on `He hasn't proved P=NP.' as long as the odds are greater than zero.
- foobarbazoo 16y agoTime to fire up Coq and really prove it.
- shadowfox 16y agoMy great grandchildren will be looking forward to the results :P
- mitko 16y agotl,dr version of his strategy (as far as I understood it) 1. For a fixed permutation construct a Viterbi-like search on the triplet assignments - if it fails it is not satisfiable. However, if it doesn't fail right away, there is still no guarantee there is an assignment. Call this structure compact triplet (CTF) or whatever. 2. Constuct a small set of permutation (at most m) for which every clause in the original CNF failing to satisfy will mean that at least one of these permutations CTFs will fail to satisfy. 3. Efficiently? combine the structures. I didn't really read it deeply but that from what I understood that seems to be the top level strategy. I'm not 100% certain about it.
- DrJosiah 16y agoThat's more or less what I got out of it as well, though I came at it from the other direction... If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following: 1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and <48M2 edges. 2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false. 3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value. 4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph). Solving part 4 is NPC. His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.
- RiderOfGiraffes 16y agoWhat we should do is generate a class of instances of 3-SAT that are expected to be hard, and then try the solver on them and see what the runtime looks like as a function of the size of the input. Recently someone claimed a polynomial-time graph coloring algorithm. I generated hard instances, their "solver" blew up. Claim debunked. It should be simple enough to do the same for this (for some definition of simple). The key lies in generating hard instances. As cperciva has said in http://news.ycombinator.com/item?id=2121837 http://news.ycombinator.com/item?id=2121837 - most instances of most NPC problems are "easy."
- larelli 16y agoI tried running the code on Pigeon Hole Problems, but it crashed. :(
- dmitrygusev 16y agoWith what error? Can you please file an issue here: https://github.com/anjlab/sat3/issues https://github.com/anjlab/sat3/issues and provide link to CNF file?
- RiderOfGiraffes 16y agoUseful link: http://en.wikipedia.org/wiki/NP-complete#Common_misconceptions http://en.wikipedia.org/wiki/NP-complete#Common_misconceptio...
- EGreg 16y agoCould it be ... P = NP? Most people suspected otherwise. Someone should really verify his algorithm on various SAT sets. But I have to say that his approach is very good and humble... he suggests he may have solved the problem -- but it is up to us to verify! I'd like to follow this further, so I bookmarked it via an upvote.
- tybris 16y agoRight, he just didn't want to submit it to a peer-reviewed journal?
- CJefferson 16y agoHaving read this paper (and being reasonably knowledgeable on the subject), I'm convinced this paper is wrong, or at least very underexplained. The algorithm uses an algorithm similar to the well-known '3-consistency', which has been shown to solve quite a lot of classes of problems, in particular some that are solved very poorly by the normal learning-based systems used in most SAT solvers. The paper aims to strengthen 3-consistency slightly, using permutations. However, while that is a reasonable strategy, it is entirely unclear to me, and unclear in the paper, while that gives poly-time solving time.
- A1kmm 16y agoIs anyone else struggling to understand theorem 2 on pages 15-16? It sounds like what they are saying is equivalent to the following: If S1 intersect S2 has a solution, and S1 intersect S3 has a solution, then the system S1 intersect S2 intersect S3 has a solution. But this is evidently false. Consider the case where the CTS included each of the following rows, and were empty everywhere else (after re-ordering the columns so the same-name columns were in the same final column): (1) 000 (2) 001 (3) 0 00 In this case, (1) and (2) are consistent, and (1) and (3) are consistent, but (2) and (3) are inconsistent. I suspect the problem they set up the induction for might not perfectly align with the theorem, but it needs more careful examination.
- deleted 16y ago[deleted]
- Tichy 16y agoI think before I would publish such a thing widely, I would ask a few friends to double check.
- mac_in_tosh 16y agoThere is an inkling prediction market on how likely this will be proved correct by the end of 2011: http://home.inklingmarkets.com/markets/34366 http://home.inklingmarkets.com/markets/34366