How to prove that Exact Cover is NP-complete using SAT?

Question

I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover.

Here's the solution from the link (where C is the clause(s), A is the universe, and F is the subsets of the universe):

C1=(x1 ∨ x2) C2=(x1 ∨ x2 ∨ x3) C3=(x2) C4=(x2 ∨ x3)

A={x1, x2, x3, C1, C2, C3, C4, p11, p12, p21, p22, p23, p31, p41, p42}

F={{p11},{p12},{p21},{p22},{p23},{p31},{p41},{p42},
X1, f={x1, p11}
X1, t={x1, p21}
X2, f={x2, p22, p31}
X2, t={x2, p12, p41}
X3, f={x3, p23}
X3, t={x3, p42}
{C1, p11},{C1, p12},{C2, p21},{C2, p22},{C2, p23},{C3, p31},{C4, p41},{C4, p422}}

I understand how this proves that it is NP-complete, but I do not understand how A and F was populated. In other words, I am unable to figure out the "algorithm" behind creating the p11...p42 variables.

Answer 1

I understand how this proves that it is NP-complete

It isn't a "proof" by any means. It's an example of how a reduction might work, but it hasn't been stated as a formal proof.

From your example, it looks like the algorithm/proof is as follows:

• The universe consists of $3$ types of elements: one element $x_i$ for every variable $i$, one element $C_j$ for every clause $j$, and one element $p_{i,j}$ for every occurrence of a variable $i$ as a literal in clause $j$.

• For every variable $i$, we create two sets; the true set and the false set. The true (resp. false) set contains $x_i$, together with, for every clause in which variable $i$ appears negated (resp. non-negated), $p_{i,j}$. As an example, if $x_1$ appears as a literal in clause $2$ and $\neg x_1$ appears in clauses $3,4$, we create the sets $\{x_1,p_{1,3},p_{1,4}\}$ and resp. $\{x_1,p_{1,2}\}$.

• For every element $p_{i,j}$, we create a set $\{C_j,p_{i,j}\}$ and a singleton set $\{p_{i,j}\}$.

As the variable true/false sets are the only sets containing $x_i$, for each variable $i$, a solution to Exact Cover must contain exactly one of the corresponding true/false sets. This gives a correspondence between the variable true/false sets selected in Exact Cover solutions and variable assignments to the SAT instance.

Moreover, any Exact Cover solution must, for every clause $j$, contain for some $i$ the set $\{C_j,p_{i,j}\}$ (since these are the only sets containing $C_j$). If $i$ is a positive literal in clause $j$, this means the false set for variable $i$ cannot be in the solution, since it also contains $p_{i,j}$. Similarly, if $i$ is a negated literal in clause $j$, we cannot have selected the true set for variable $i$. Thus, variable $i$ satisfies clause $j$ in the variable assignment corresponding to the selected variable true/false sets.

Conversely, given a satisfying assignment to the SAT instance, we can simply select the variable true/false sets corresponding to the assignment. For every clause we can select any set $\{C_j,p_{i,j}\}$ for which $i$ is a satisfying literal of clause $j$. This covers the $x_i$'s and $C_j$'s. The remaining $p_{i,j}$'s can be covered by singletons.