[Rule] NOT-ALL-EQUAL 3SAT to SET SPLITTING #841
Description
Source: NOT-ALL-EQUAL 3SAT
Target: SET SPLITTING
Motivation: Establishes NP-completeness of SET SPLITTING via polynomial-time reduction from NAE3SAT. The reduction is essentially an identity/reinterpretation: each clause becomes a subset, each variable becomes a universe element, and a NAE-satisfying assignment is exactly a set splitting. This is one of the most natural reductions in the G&J hierarchy — Set Splitting is the hypergraph 2-colorability reformulation of NAE-SAT.
Reference: Garey & Johnson, Computers and Intractability, SP4, p.221
GJ Source Entry
[SP4] SET SPLITTING
INSTANCE: Collection C of subsets of a finite set S.
QUESTION: Is there a partition of S into two subsets S_1 and S_2 such that no subset in C is entirely contained in either S_1 or S_2?
Reference: [Lovasz, 1973]. Transformation from NOT-ALL-EQUAL 3SAT. The problem is also known as HYPERGRAPH 2-COLORABILITY.
Comment: Remains NP-complete even if all c∈C have |c|≤3. Solvable in polynomial time if all c∈C have |c|≤2 (becomes GRAPH 2-COLORABILITY).
Reduction Algorithm
Summary:
Given a NAE3SAT instance with variables V = {v_1, ..., v_n} and clauses C = {c_1, ..., c_m} (each clause has exactly 3 literals), construct a SET SPLITTING instance as follows:
-
Universe: S = {v_1, ..., v_n, ¬v_1, ..., ¬v_n}. Include both positive and negative copies of each variable (2n elements total).
-
Complementarity subsets: For each variable v_i, add the subset {v_i, ¬v_i} to the collection. This forces v_i and ¬v_i into different partitions, encoding Boolean complementarity.
-
Clause subsets: For each clause c_j = (l_1, l_2, l_3), add the subset {l_1, l_2, l_3} to the collection. Each literal l_k is the corresponding element in S (positive or negative copy).
-
Correctness: A set splitting (partition into S_1, S_2 with no monochromatic subset) exists if and only if the NAE3SAT formula is satisfiable:
- Complementarity subsets ensure a consistent truth assignment (v_i and ¬v_i are in different partitions)
- Clause subsets ensure no clause is all-true or all-false (not-all-equal)
-
Solution extraction: Given a set splitting S_1, S_2: for each variable v_i, if v_i ∈ S_1 then set v_i = true, else set v_i = false. The complementarity subsets guarantee consistency. The clause subsets guarantee each clause has at least one true and one false literal.
Special case (monotone NAE3SAT): When the formula has no negated literals, the reduction is a pure identity: S = V, and each clause {v_i, v_j, v_k} becomes a subset directly. No complementarity subsets are needed.
Key invariant: The NAE3SAT instance is satisfiable if and only if the constructed Set Splitting instance has a valid partition.
Size Overhead
Symbols:
- n = number of variables in the NAE3SAT instance
- m = number of clauses
| Target metric (code name) | Polynomial (using symbols above) |
|---|---|
universe_size |
2 * num_variables |
num_subsets |
num_clauses + num_variables |
Derivation: The universe contains 2n elements (one per literal). The collection contains m clause-subsets plus n complementarity subsets, for m + n total subsets. For monotone NAE3SAT, the overhead is simply n elements and m subsets (identity).
Validation Method
- Closed-loop test: construct a NAE3SAT instance, reduce to Set Splitting, solve with BruteForce, extract the truth assignment from the partition, verify each clause has at least one true and one false literal
- Check that a satisfiable NAE3SAT instance yields a valid set splitting
- Check that an unsatisfiable NAE3SAT instance yields no valid set splitting
- Verify complementarity: for each variable, its positive and negative literals are in different partition halves
Example
Source instance (NAE3SAT):
Variables: {x_1, x_2, x_3, x_4}
Clauses:
- c_1 = (x_1, x_2, x_3)
- c_2 = (¬x_1, x_3, x_4)
- c_3 = (x_2, ¬x_3, ¬x_4)
- c_4 = (x_1, ¬x_2, x_4)
Target instance (Set Splitting):
Universe S = {x_1, x_2, x_3, x_4, x̄_1, x̄_2, x̄_3, x̄_4} (8 elements)
Collection C:
- Complementarity: {x_1, x̄_1}, {x_2, x̄_2}, {x_3, x̄_3}, {x_4, x̄_4}
- Clause subsets: {x_1, x_2, x_3}, {x̄_1, x_3, x_4}, {x_2, x̄_3, x̄_4}, {x_1, x̄_2, x_4}
Satisfying partition:
S_1 = {x_1, x̄_2, x_3, x̄_4}, S_2 = {x̄_1, x_2, x̄_3, x_4}
(Corresponds to assignment: x_1=T, x_2=F, x_3=T, x_4=F)
Verification:
- {x_1, x̄_1}: x_1 ∈ S_1, x̄_1 ∈ S_2 → split ✓
- {x_2, x̄_2}: x̄_2 ∈ S_1, x_2 ∈ S_2 → split ✓
- {x_3, x̄_3}: x_3 ∈ S_1, x̄_3 ∈ S_2 → split ✓
- {x_4, x̄_4}: x̄_4 ∈ S_1, x_4 ∈ S_2 → split ✓
- {x_1, x_2, x_3}: x_1 ∈ S_1, x_2 ∈ S_2 → split ✓
- {x̄_1, x_3, x_4}: x_3 ∈ S_1, x̄_1 ∈ S_2 → split ✓
- {x_2, x̄_3, x̄_4}: x̄_3 ∈ S_2, x̄_4 ∈ S_1 → split ✓
- {x_1, x̄_2, x_4}: x_1 ∈ S_1, x_4 ∈ S_2 → split ✓
NAE check: x_1=T, x_2=F, x_3=T, x_4=F
- c_1 = (T, F, T) → not all equal ✓
- c_2 = (F, T, F) → not all equal ✓
- c_3 = (F, F, T) → not all equal ✓
- c_4 = (T, T, F) → not all equal ✓
References
- [Lovasz, 1973]: [
Lovasz1973] Laszlo Lovasz (1973). "Coverings and colorings of hypergraphs". In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 3–12. Utilitas Mathematica Publishing.