In computer science, the partition problem is the task of deciding whether a given multiset 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".
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.
Read more about Partition Problem: Examples, Pseudo-polynomial Time Algorithm, Special Case of The Subset-sum Problem, Hard Instances, The k-partition Problem, Alternative Forms of The Problem, See Also
Famous quotes containing the word problem:
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)