Course contentsShow
← Computer Science
Lesson 1926 of 2,87243. Complexity TheoryFree lesson

Partition Problem

Dividing a set of integers into two subsets with equal sums and proving NP-completeness.

Partition Problem

You'll learn how to formally define the Partition Problem, understand why it's NP-complete, and see how it connects to other hard computational problems.

What is the Partition Problem?

Imagine you have a set of positive integers and you want to split them into two groups so that each group has exactly the same sum. That's the Partition Problem: given a set of integers, can you divide them into two disjoint subsets with equal sums?

For example, the set {1, 5, 11, 5} has a valid partition: {1, 5, 5} and {11}, both summing to 11. But the set {1, 2, 3, 9} cannot be partitioned evenly.

Why This Matters

The Partition Problem is NP-complete, meaning:

  1. It's in NP because if someone gives you a proposed partition, you can quickly verify it works by summing both subsets
  2. It's NP-hard because every other NP problem can be reduced to it in polynomial time

The NP-Completeness Proof Sketch

The Partition Problem's NP-completeness is typically proven by reduction from Subset Sum. Given a Subset Sum instance (does any subset sum to target value T?), you can construct a Partition instance by adding a new element with value S - 2T, where S is the total sum of all elements. If the original set had a subset summing to T, the new set can be partitioned; conversely, any partition of the new set reveals a subset summing to T in the original.

This establishes Partition as "at least as hard" as Subset Sum, which is already known to be NP-complete.

Practical Implications

While Partition looks simple, no known algorithm solves it efficiently for all cases. The best approaches either use exponential-time exact algorithms or polynomial-time approximations.

Key Takeaway: The Partition Problem asks if a set of integers can be split into two equal-sum subsets; it's NP-complete, requiring verification of guessed solutions rather than efficient discovery.