Groupe d’études et de recherche en analyse des décisions

G-90-14

On Transforming the Satisfiability and Maximum Satisfiability Problems into Set Covering Problems

et

We show that the satisfiability and maximum satisfiability problems can be transformed into set covering problems at the expense of acceptable increase of size. Given a conjunctive normal form of n atomic propositions and m clauses, the satisfiability and maximum satisfiability problems can be transcribed into set covering problems of 2n variables and m + n constraints, and 2n + m variables and m + n constraints, respectively.

, 10 pages