tag:blogger.com,1999:blog-6555947.post7198015614717393477..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: The Joys of NAE-SATSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-6555947.post-13250255124622953762012-08-25T18:54:01.596-06:002012-08-25T18:54:01.596-06:00Not only Planar-NAE-3SAT is in P, counting the num...Not only Planar-NAE-3SAT is in P, counting the number of solutions too (contrast this with 2SAT for example). See http://people.seas.harvard.edu/~valiant/holographic11-07.pdfDiegonoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-86363792850485088292011-11-15T13:29:54.921-07:002011-11-15T13:29:54.921-07:00@Anonymous: MAX-3SAT is in fact hard to approximat...@Anonymous: MAX-3SAT is in fact hard to approximate to within a factor of 7/8.Blue Dreamz....https://www.blogger.com/profile/07333041717393048510noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-83789313907894567772011-11-08T21:52:56.378-07:002011-11-08T21:52:56.378-07:00Is Cubic-Monotone-NAE-3SAT NP-complete? (i.e. when...Is Cubic-Monotone-NAE-3SAT NP-complete? (i.e. when every variable is in exactly three clauses)<br />This is true for Planar 1-in-3 SAT (http://arxiv.org/abs/math/0003039).Diegonoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-54142157110559211752011-11-08T21:41:21.980-07:002011-11-08T21:41:21.980-07:00Another interesting thing about NAE-3-SAT is that ...Another interesting thing about NAE-3-SAT is that there is a simple physical construction of it: the so called "Logic Engine" , which helps prove NP-completeness for various graph drawing problems.<br />(see http://dx.doi.org/10.1016/0020-0190(87)90173-6 or http://sydney.edu.au/engineering/it/~cmurray/22Murray.pdf)Diegonoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-83027820275725978862010-05-07T14:11:30.846-06:002010-05-07T14:11:30.846-06:00Is MAX-NAE 3SAT difficult to approximate within a ...Is MAX-NAE 3SAT difficult to approximate within a factor 1-eps (for some eps>0) like MAX-3SAT ? If yes, How can one prove it ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-82556041563194387752008-11-05T22:12:00.000-07:002008-11-05T22:12:00.000-07:00do you mean NAE-SAT to 3SAT or the other way aroun...do you mean NAE-SAT to 3SAT or the other way around ? <BR/><BR/>reducing SAT to NAE-SAT is quite easy. you just have to express the extra condition as a clause. To make this all 3-SAT friendly takes a bit more work.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-29497973972067240482008-11-03T07:27:00.000-07:002008-11-03T07:27:00.000-07:00You are right with that property. I found it very ...You are right with that property. I found it very useful, too. Do you also know how the reduction from NAE-SAT to 3-SAT actually works? The original paper of Schaefer(The complexity of satisfiability problems, 1977) you are always referred to, doesn't give the reduction function.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-67531505821358184412008-03-21T08:22:00.000-06:002008-03-21T08:22:00.000-06:00It's really funny - I just spent a day or two stud...It's really funny - I just spent a day or two studying NAE-3-SAT and its use is proving NP-hardness of combinatorial optimization problems. From whatever limited experience I have, this problem has been more useful for reductions rather than using 3-SAT, and your post very well outlines the reason for this. Many thanks for sharing your insights on this aspect!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-413924194419097262008-03-20T20:10:00.000-06:002008-03-20T20:10:00.000-06:00That's a neat property, and I wasn't aware of it. ...That's a neat property, and I wasn't aware of it. thanks !Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-66408566214720320602008-03-20T18:13:00.000-06:002008-03-20T18:13:00.000-06:00Here's another interesting property of NAE-3-SAT. ...Here's another interesting property of NAE-3-SAT. Its maximizing version (MAX-NAE-3-SAT) has a non-trivial exact algorithm: using fast matrix multiplication, it can be solved in 1.8^n time. Such an algorithm is not known for MAX-3-SAT.<BR/><BR/>The algorithm relies on the fact that one can represent the NAE constraint on three variables with a degree-two polynomial.ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.com