Partition

Input

Finite set $A$ and a size $s(a) \in \mathbb{Z}^{+}$ for each $a \in A$.

Question

Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \sum_{a \in A - A'} s(a)$?

Classes

• NP-complete

Comments

Remains NP-complete even if we require that $|A'| = \frac{|A|}{2}$, or if the elements in $A$ are ordered as $a_1, a_2, \dots, a_{2n}$ and we require that $A'$ contains exactly one of $a_{2i-1}$, $a_{2i}$ for $1 \leq i \leq n$. However, all these problems can be solved in pseudo-polynomial time by dynamic programming.

Proofs

NP-complete

Transformation from 3-Dimensional Matching (Karp, 1972).

Reducible from

• 3-Dimensional Matching

Reducible to

• Knapsack
• Multiprocessor Scheduling

References

• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9