The set splitting problem asks, for a collection 
of subsets of a finite set 
, whether 
can be partitioned into two sets 
and 
such that every member of 
meets both parts. In other words, it asks whether there is
a set partition 
satisfying
 |
for every 
.
Equivalently, the members of 
are to be colored with two colors
so that no member of 
is monochromatic. The decision
problem is NP-complete (Lovász
1973).
