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:
“It was a comfort in those succeeding days to sit up and contemplate the majestic panorama of mountains and valleys spread out below us and eat ham and hard boiled eggs while our spiritual natures reveled alternately in rainbows, thunderstorms, and peerless sunsets. Nothing helps scenery like ham and eggs.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“The child begins life as a pleasure-seeking animal; his infantile personality is organized around his own appetites and his own body. In the course of his rearing the goal of exclusive pleasure seeking must be modified drastically, the fundamental urges must be subject to the dictates of conscience and society, urges must be capable of postponement and in some instances of renunciation completely.”
—Selma H. Fraiberg (20th century)