Hard Instances
Sets with only one, or no partitions tend to be hardest (or most expensive) to solve compared to their input sizes. When the values are small compared to the size of the set, perfect partitions are more likely. The problem is known to undergo a "phase transition"; being likely for some sets and unlikely for others. If m is the number of bits needed to express any number in the set and n is the size of the set then tends to have many solutions and tends to have few or no solutions. As n and m get larger, the probability of a perfect partition goes to 1 or 0 respectively. This was originally argued based on empiricial evidence by Gent and Walsh, then using methods from statistical physics by Mertens, and later proved by Borgs, Chayes, and Pittel.
Read more about this topic: Partition Problem
Famous quotes containing the words hard and/or instances:
“Monday’s child is fair in face,
Tuesday’s child is full of grace,
Wednesday’s child is full of woe,
Thursday’s child has far to go,
Friday’s child is loving and giving,
Saturday’s child works hard for its living;
And a child that is born on a Christmas day,
Is fair and wise, good and gay.”
—Anonymous. Quoted in Traditions, Legends, Superstitions, and Sketches of Devonshire, vol. 2, ed. Anna E.K.S. Bray (1838)
“There are few instances of the exercise of particular virtues which seem harder to attain to, or which appear more amiable and engaging in themselves, than those of moderation and the forgiveness of injuries.”
—Laurence Sterne (1713–1768)