When all else fails, the "standard" way of proving a problem NP-hard is to go back to the basics, i.e 3SAT. One particularly quirky variant that I quite enjoy is NAE-SAT:
As usual, you're given an instance of satisfiability with clauses and variables, and you want to check if there's a satisfying instance. In NAE-SAT, the extra catch is that in no clause are you allowed to have all literals set to TRUE. Since no clause can have all literals set to FALSE, you get the name 'Not-All-Equal-SAT', or NAE-SAT.Like SAT, NAE-SAT is NP-Complete, and remains so if you restrict clauses to containing 3 literals (i.e NAE-3SAT). Other interesting properties:
- NAE-3SAT is still NP-complete in its monotone variant (i.e if all variables appear unnegated). This is in contrast to SAT, which is trivial in that case. This property is particularly handy if you don't want to deal with how to ensure consistency between a variable and its negation when making a gadget.
- If X is a satisfying assignment for NAE-SAT, then so is X' (the complement of X). This is again because of the NAE-property. A clause that's satisfied with one literal becomes one that's satisfied with two literals, and so on. Since no clause has all three literals set to TRUE, no clause becomes unsatisfied. This is useful because when you assume that the problem has a satisfying instance, you have two instances you can use (we used this trick in a paper a while back).
- Unusually, and unlike other SAT variants, Planar-NAE-SAT is in P. This is a surprising result due to Bernard Moret, and prevents us from using NAE-SAT for many geometric problems where planarity is a useful tool (but if you can handle crossings, you're ok).
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.
ReplyDeleteThe algorithm relies on the fact that one can represent the NAE constraint on three variables with a degree-two polynomial.
That's a neat property, and I wasn't aware of it. thanks !
ReplyDeleteIt'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!
ReplyDeleteYou 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.
ReplyDeletedo you mean NAE-SAT to 3SAT or the other way around ?
ReplyDeletereducing 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.
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 ?
ReplyDeleteAnother 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.
ReplyDelete(see http://dx.doi.org/10.1016/0020-0190(87)90173-6 or http://sydney.edu.au/engineering/it/~cmurray/22Murray.pdf)
Is Cubic-Monotone-NAE-3SAT NP-complete? (i.e. when every variable is in exactly three clauses)
ReplyDeleteThis is true for Planar 1-in-3 SAT (http://arxiv.org/abs/math/0003039).
@Anonymous: MAX-3SAT is in fact hard to approximate to within a factor of 7/8.
ReplyDeleteNot 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.pdf
ReplyDelete