In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset "S" of positive integers can be partitioned into two subsets "S"1 and "S"2 such that the sum of the numbers in "S"1 equals the sum of the numbers in "S"2. 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".