Reducing 3SAT to a Set Splitting Problem

Question

I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the fact if it is possible to color the items red and blue so that each set $S_i$ contains at least one red item and at least one blue item.

I know this this problem is in NP and it is fairly simple to prove (at least that is what I think).

I actually want to prove that the problem is NP hard by reduction from 3SAT. I want to be able to convert an instance of 3SAT into an instance of the aforementioned set-splitting such that a yes instance of 3SAT get mapped to a yes instance of set-splitting and vice versa.

I have a basic intuition about how I can do this: given a 3SAT formula $f$ on $n$ variables I will create $2n+1$ items. One to denote each $x_i$ one for each $\overline{x_i}$ and an extra item. I am not quite sure how to proceed beyond this basic intuition. This might be a gap in my understanding of the problem. Is this the right way to approach this? If so, how can I use this intuition to actually prove that this is NP hard by way of reduction from 3SAT?

Thank you!

Answer 1

Your problem is a generalization of NAE-SAT, an NP-complete version of SAT (see for example David Witmer's lecture notes in which we want each clause to have at least one satisfied literal and at least one falsified literal.

In order to convert NAE-SAT to your problem, identify literals with items, have a set per clause, and also have a set per variable, forcing the two literals to get opposite colors. Details left to you.