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:
“One of the main things that interfere with our joy is the belief that if we try hard enough, read the right books, follow the right advice, and buy the right things, we could be perfect parents. If we are good enough as parents, our children will be perfect too.... Unfortunately, what comes from trying to live out this philosophy is not perfect children but worried parents.”
—Lawrence Kutner (20th century)
“The prime lesson the social sciences can learn from the natural sciences is just this: that it is necessary to press on to find the positive conditions under which desired events take place, and that these can be just as scientifically investigated as can instances of negative correlation. This problem is beyond relativity.”
—Ruth Benedict (1887–1948)