## Exercise ‹3›:

SAT $\leq$ SET COVERING
Reduce the SAT problem to the SET COVERING problem. These problems are defined as follows:
• SAT: given a boolean formula $F$ in conjunctive normal form, is $F$ satisfiable?
More formally, this problem can be defined as the following set:
$\{ F=C_1\wedge\ldots\wedge C_n \mid F\text{ satisfiable} \}$
• SET COVERING: given a natural $k$ and a collection of finite sets $S_1,\ldots,S_n$, is there a cover for $S_1\cup\ldots\cup S_n$ of size at most $k$? In other words, is there a selection of at most $k$ of such sets $S_i$ such that their union equals the union of all the sets $S_1,\ldots,S_n$?
More formally, this problem can be defined as the following set:
$\{ \langle k,\langle S_1,\ldots,S_n\rangle\rangle \mid S_1,\ldots,S_n\text{ finite sets}\;\wedge\;\exists \{i_1,\ldots,i_m\}\subseteq\{1,\ldots,n\}: (m\leq k\;\wedge\;(S_1\cup\ldots\cup S_n)=(S_{i_1}\cup\ldots\cup S_{i_m})) \}$
The input and output of the reduction conform to the following data types:
• in: struct {
numvars: int
clauses: array of array of int
}

The input is a boolean formula in conjunctive normal form: in.numvars specifies the number of variables occurring in the formula, and in.clauses is the list of clauses. Each clause is a list of literals, and each literal is a positive or negative integer: a positive integer $x$ represents the $x$’th variable, and a negative integer $-x$ represents the negation of the $x$’th variable. Such an $x$ takes values between $1$ and in.numvars.

Note: The input has at least one clause, every clause has at least one literal, and there are no repeated literals in a clause. Thus, in.numvars is at least $1$.
• out: struct {
k: int
sets: array of array of string
}

The output is a natural number out.k and a list of sets out.sets. The elements of the sets are integers or strings.

Note: If the output out.k is negative, then no such set covering exists. Empty sets are ignored.
Authors: Carles Creus / Documentation:
 main { // Write your reduction here... } To be able to submit you need to either log in, register, or become a guest.