# How to reduce 3-SAT to Set Splitting

I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following:

Given a collection $$C$$ of subsets of a finite set $$S$$, state if there's a partition into two subsets $$S_1$$ and $$S_2$$ such that no subset in $$C$$ is entirely contained in either $$S_1$$ or $$S_2$$?

The book says a Not-All-Equal-3SAT should be reduced to the stated problem to prove the NP-completeness sof the latter, but I can't seem to find a way. How to reduce NAE-3SAT to this problem?

Extra Question: how does one write an algorithm for such a partition?

I am aware about this discussion, but I couldn't find a link between reduction such as NAE-3SAT - 3COL - Set Splitting. If you can, please explain it.

Given an instance $$C_1 \lor \cdots \lor C_m$$ of NAE3SAT, we construct an instance of your problem as follows:
• $$S$$ is the set of literals.
• $$C$$ consists of the sets $$C_1,\ldots,C_m$$ (considered as sets of literals) together with the sets $$\{ x_i, \lnot x_i \}$$ for each variable $$x_i$$.
A valid solution to this instance consists of a partition of $$S$$ into two sets $$S_1,S_2$$, which we can think of as a truth assignment to the variables: $$x_i \in S_1$$ iff $$\lnot x_i \in S_2$$. Think of the literals in $$S_1$$ as true. Then each clause must contain both true literals (literals in $$S_1$$) and false literals (literals in $$S_2$$), i.e., is should be satisfied as NAE.