Is the Subset Sum Problem Truly Solved by Generating Large Random Sets?

[LolipopDragon]

Hello,

My hobby is to design algorithms especially data compression algorithms, but when I can't find a solution to my problems I usually go find myself a different problem to solve because it helps me think differently or maybe it lights a bulb about the original problem …today I stumbled on the P vs NP problem for the first time, 5 minutes reading through Wikipedia I found the Subset Sum problem https://en.wikipedia.org/wiki/Subset_sum_problem which Wikipedia mentions is an important problem and is NP Complete…. So I decided to try and write an algorithm that finds the elements of any set of random integers that sum up to any random number S Fast, first what I did is generate an array of one million random numbers between one and one million, then told the computer to generate a random number also between one and one million, then applied my algorithm which finds elements in the array that sum to the random number S in seconds. The Bigger the set of RANDOM numbers the easier to find a solution!

So the answer was too simple and easy, my question is what am I missing/doing wrong here?

 

[pwsnafu]

So, where's your proof that your algorithm runs in polynomial time?
Secondly, a million is a very small number. Efficient algorithms are known for small N. Try your algorithm with, say, 2 raised to the power of a million. I doubt that your algorithm will terminate.
Thirdly, you said you generated a million numbers, but with a upper bound of a million on each number. Well, there's a very high probability that you generated the majority of numbers from 1 to 1,000,000. So yeah, obviously any algorithm should be fast. Try again but remove the million upper limit.

Edit: This

The Bigger the set of RANDOM numbers the easier to find a solution!

indicates that it's the third point that's making it easy for you.

 

[Samy_A]

From the Wikipedia article:

"For the case that each x_i is positive and bounded by a fixed constant C, Pisinger found a linear time algorithm having time complexity O(NC)."

 

[LolipopDragon]

From the Wikipedia article:

"For the case that each xi is positive and bounded by a fixed constant C, Pisinger found a linear time algorithm having time complexity O(NC)."

Does this mean i should not pursue this any longer?

So, where's your proof that your algorithm runs in polynomial time?
Secondly, a million is a very small number. Efficient algorithms are known for small N. Try your algorithm with, say, 2 raised to the power of a million. I doubt that your algorithm will terminate.
Thirdly, you said you generated a million numbers, but with a upper bound of a million on each number. Well, there's a very high probability that you generated the majority of numbers from 1 to 1,000,000. So yeah, obviously any algorithm should be fast. Try again but remove the million upper limit.

Edit: This

indicates that it's the third point that's making it easy for you.

thanks for your input, i will remove the upper bounds and test again, one thing tho,

I don’t know where/how you came up with that number (2 power million (around 300000 zeros of numbers to store!)) but I don’t think any pc or any ram can handle even storing such amount of number to try and perform operations on it, the maximum array size in my programming language is 16 million, I could use multiple arrays and cycle through them but even then the number wouldn’t come close to 2 power million. anyway i think I've cleared my head and its time to head back to data compression...

Edit: yes, you are correct, after removing the upper limits the algorithm did not yield the desired results...

 

[fresh_42]

Does this mean i should not pursue this any longer?

I don't know your algorithm. Just to mention: you are not allowed to use random guesses.

 

[Samy_A]

Does this mean i should not pursue this any longer?

Pisinger's algorithm, published in 1995, does seem to address the case you treated. It's an interesting paper by the way, if you like this subject you may like his paper.