The Easiest Hard Problem (2002) • Hacker News Board

Re: The Easiest Hard Problem (2002)

#11

Post by malnourish » Fri, Aug 07, 2015, 2:24 PM UTC

vog wrote: post #9

malnourish wrote: post #7

At first his language was a little confusing -- when I saw "set" and then saw two 2s listed in his set. Are "set" and "multiset" often this interchangeable?

No, they aren't. This is just sloppy wording in the article. The concept of sets is deeply established in mathematics and when you talk about multisets rather than sets you have to state this explicitly.

That's what I thought -- it was what I was taught in school. But I was also taught that no one can agree on terminology.

Re: The Easiest Hard Problem (2002)

#12

Post by noobie » Fri, Aug 07, 2015, 2:24 PM UTC

vog wrote: post #5

Strilanc wrote: post #3

Earlier quoted context omitted.

Why is it easy to prove that this particular set of numbers can be broken into equal subsets?

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

> The sum of all 90 numbers is Why? (Obviously you wouldn't compute it so what's the "trick"?)

Re: The Easiest Hard Problem (2002)

#13

Post by SilasX » Fri, Aug 07, 2015, 2:28 PM UTC

Great article! This gives an excellent overview of NP-complete problems, the difficulty of constructing hard instances, the critical ratio in determining the solution count, and the analogy to physical systems' phase transitions. Also gives some intuition on why the greedy algorithms can be good enough in pracitce and when they wouldn't be.

Re: The Easiest Hard Problem (2002)

#14

Post by SilasX » Fri, Aug 07, 2015, 2:31 PM UTC

noobie wrote: post #12

vog wrote: post #5

Earlier quoted context omitted.

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

> The sum of all 90 numbers is Why? (Obviously you wouldn't compute it so what's the "trick"?)

The sum of 90 numbers in this context is considered to be easy (esp relative to finding the sum of many possible subsets).

Re: The Easiest Hard Problem (2002)

#15

Post by vog » Fri, Aug 07, 2015, 2:36 PM UTC

SilasX wrote: post #14

noobie wrote: post #12

Earlier quoted context omitted.

> The sum of all 90 numbers is Why? (Obviously you wouldn't compute it so what's the "trick"?)

The sum of 90 numbers in this context is considered to be easy (esp relative to finding the sum of many possible subsets).

That's true. However, it is also easy to estimate that sum rather than calculating it exactly, so I adjusted my proof accordingly.

Re: The Easiest Hard Problem (2002)

#16

Post by vog » Fri, Aug 07, 2015, 2:38 PM UTC

unlikelymordant wrote: post #4

Strilanc wrote: post #3

Earlier quoted context omitted.

Why is it easy to prove that this particular set of numbers can be broken into equal subsets?

Given the subsets it is easy to verify the subsets come from the set and their sum is the same. Finding them is hard.

I'm afraid you missed the point.

Re: The Easiest Hard Problem (2002)

#17

Post by bit-player » Fri, Aug 07, 2015, 2:42 PM UTC

PDF version here: http://bit-player.org/bph-publications/AmSci-2002-03-Hayes-N... (from the author's website)

Re: The Easiest Hard Problem (2002)

#18

Post by phkahler » Fri, Aug 07, 2015, 2:50 PM UTC

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example:

split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7.

split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5) has a difference of 1 so don't go there.

5x11 - 2x3x7 = 13

Is it always possible to create a partition that produces the N+1th prime?

AFAIK this is a problem of my own conjuring, but I also know that most such things already exist and have a name.

Re: The Easiest Hard Problem (2002)

#19

Post by skyrockect9 » Fri, Aug 07, 2015, 2:55 PM UTC

The first heuristic algorithm that jumps to my mind to solve this problem goes like this: First sort the numbers into a list. Second take elements from the head of the list to construct a subset A. Third take elements from the tail to construct a subset B The second and third steps are done in such a way that the sum of A and B are nearly equal. Then one can hope that this procedure make the elements that are still in the list to be near identical and so allow you to construct nearly identical sums.

Re: The Easiest Hard Problem (2002)

#20

Post by skyrockect9 » Fri, Aug 07, 2015, 2:59 PM UTC

skyrockect9 wrote: post #19

The first heuristic algorithm that jumps to my mind to solve this problem goes like this: First sort the numbers into a list. Second take elements from the head of the list to construct a subset A. Third take elements from the tail to construct a subset B The second and third steps are done in such a way that the sum of A and B are nearly equal. Then one can hope that this procedure make the elements that are still i…

The hope is that the remaining elements in the list l are similar in the sense that max(l)/min(l) is small, the heuristic could be improved one you try to make a trade off between max(l)/min(l) in the list and the difference between sum A and sum B.