I need to reduce Partition of a Set from 3-SAT NAE to prove that set partitioning is NP-Complete.
I have this:
Given an instance of NAE-3-SAT, the reduction builds an instance of the set partition problem in the following way:
First, for each variable xi in NAE-3-SAT, the reduction creates two elements in S, xi and ~xi.
Then, for each clause Ci = (l1 ∨ l2 ∨ l3) in NAE-3-SAT, the reduction creates a subset Ai in C consisting exactly of the literals in Ci. The literals could be xi or ~xi depending on whether the variable is negated in the clause.
Furthermore, for each variable xi, the reduction creates a subset Bi in C consisting of xi and ~xi.
Thus, an instance of the set partition problem has been constructed from an instance of NAE-3-SAT in polynomial time.
Now, it must be shown that this reduction is valid, that is, the NAE-3-SAT instance is satisfiable if and only if there exists a partition of S into two subsets S1 and S2 that satisfy the conditions of the set partition problem.
(⇒) Assume there exists a truth assignment to the variables in NAE-3-SAT that satisfies all clauses. We assign all variables that are assigned true to S1 and the others to S2. Since the assignment satisfies NAE-3-SAT, for each clause Ci, there is at least one literal that is true and one that is false, therefore Ai intersects both S1 and S2. Moreover, for each variable xi, xi and ~xi cannot both be true or both false, therefore Bi intersects both S1 and S2.
(⇐) Now, assume there exists a partition of S into two subsets S1 and S2 that satisfy the conditions of the set partition problem. Given the way S and C were constructed, this means that for each variable xi, xi and ~xi are in different subsets, and for each clause Ci, not all literals are in the same subset. Then, we can construct a truth assignment to the variables such that xi is true if and only if xi is in S1. Since not all literals of each clause are in the same subset, this assignment satisfies NAE-3-SAT.
Therefore, the reduction is valid and the set partition problem is NP-complete.