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 of positive integers.
Question: does there exist such that

Target

Let

Then 2-partition asks whether some subset of sums to . 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.