Thursday, March 20, 2008

The Joys of NAE-SAT

(ed: the point of this post will be completely lost on you if you don't often prove NP-Completeness results)

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).
Anyone for a paean to ONE-in-THREE-SAT ?

Disqus for The Geomblog