Partition problem is NP-complete

Dependencies:

1. Subset-sum is NP-complete

The partition problem is in NP because we can use the partitioning as a certificate. To validate the certificate, just check if the partitions are disjoint, span the original set and have the same sum.

The partition problem is NP-hard because it can be reduced in polynomial time to the subset-sum problem. Proving this theorem is given as exercise 34.5-5 in CLRS edition 3, page 1101. See solutions by Bodnar and Lohr.

Dependency for:

1. 1BP is (1.5-ε)-inapprox

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. /complexity/np-completeness/3-sat
2. Subset-sum is NP-complete