patternMinor
CNF SAT conversions
Viewed 0 times
satconversionscnf
Problem
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?
Solution
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.)
(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.)
Context
StackExchange Computer Science Q#18793, answer score: 5
Revisions (0)
No revisions yet.