I am interested in reductions from 3-CNF boolean expressions to similar restricted forms. For example, I am interested in knowing how to reduce a 3-CNF formula to another 3-CNF formula where each variable appears in at most $b$ clauses. I observed this is used in MAX-SAT so I am interested in knowing such reductions. Is there a paper/book that contains descriptions of such forms and their properties?


Feige's classical paper A threshold of ln n for approximating set cover shows that 3SAT-5 is NP-complete; this is the version of 3SAT in which each variable occurs exactly 5 times. The general trick here is to include clauses stating $a \leftrightarrow b$, thus allowing "duplication" of variables. If you're very careful, you can get to the symmetric situation considered by Feige.

(On the subject of set cover, recently Dinur and Steurer showed that it is NP-hard to approximate set cover better than $\ln n$, using a reduction of Moshkovitz. Feige's result relies on a stronger assumption.)

| cite | improve this answer | |
  • $\begingroup$ I am pretty new to the field of SAT solving, so do you know where can I find descriptions of various forms, possibly at one place? I've tried looking at Handbook of Satisfiability, but couldn't find it there. I guess it might be the case that this is just spread around as there are probably a lot of forms. $\endgroup$ – bellpeace Dec 10 '13 at 4:11
  • 2
    $\begingroup$ My guess is that this is too elementary to be discussed anywhere, though you can check Garey & Johnson or any other collection of NP-complete problems. $\endgroup$ – Yuval Filmus Dec 10 '13 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.