Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Set splitting problem
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the set splitting problem is the following <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a>: given a family <i>F</i> of subsets of a finite set <i>S</i>, decide whether there exists a partition of <i>S</i> into two subsets <i>S1</i>, <i>S2</i> such that all elements of <i>F</i> are split by this partition, i.e., none of the elements of <i>F</i> is completely in <i>S1</i> or <i>S2</i>. Set Splitting is one of <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss">Garey & Johnson's</a> classical <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problems. The problem is sometimes called <a href="/facts/Property_B/ru8dfKfr">hypergraph 2-colorability</a>. </p>