Partition problem

In number theory and computer science, the partition problem, or number partitioning,[1] is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".[2][3]

There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.[4]

The partition problem is a special case of two related problems:

  • In the subset sum problem, the goal is to find a subset of S whose sum is a certain target number T given as input (the partition problem is the special case in which T is half the sum of S).
  • In multiway number partitioning, there is an integer parameter k, and the goal is to decide whether S can be partitioned into k subsets of equal sum (the partition problem is the special case in which k = 2).

However, it is quite different to the 3-partition problem: in that problem, the number of subsets is not fixed in advance – it should be |S|/3, where each subset must have exactly 3 elements. 3-partition is much harder than partition – it has no pseudo-polynomial time algorithm unless P = NP.[5]

  1. ^ Korf 1998.
  2. ^ Hayes, Brian (March–April 2002), "The Easiest Hard Problem" (PDF), American Scientist, vol. 90, no. 2, Sigma Xi, The Scientific Research Society, pp. 113–117, JSTOR 27857621
  3. ^ Mertens 2006, p. 125.
  4. ^ Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI.
  5. ^ Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.