2-Partition Problem

computation scheduling

Definition

2-Partition Problem

The 2-partition problem is a decision problem that asks whether a multiset of positive integers can be split into two subsets with equal sum.

Instance: a multiset $S$ of positive integers.
Question: does there exist $A\subseteq S$ such that

$$\sum _{a\in A}a=\sum _{b\in S\setminus A}b?$$

Target

Let

$$T=\frac{1}{2}\sum _{s\in S}s.$$

Then 2-partition asks whether some subset of $S$ sums to $T$. Thus it is a special case of the subset sum problem.

Hardness

Weak NP-hardness

2-partition is weakly NP-hard. Its hardness comes from the numerical sizes of the input values.