3 ms·

Show HN: I solved the subset sum problem in polynomial time

3 points by zzxxyyaabbcc 5y ago

https://pastebin.com/j6bqLn8E I think I solved the subset sum problem, a NP-Complete problem. I compared the output of smaller sets to existing algorithms and the results match. Obviously, I cant compare larger sets due to the time complexity of existing algorithms. So my question is, what is the best path forward? I'll solve a few more of your sets below for more proof, although some sets/goals require more memory than my computer has. For now I wont share the details of the algorithm for obvious reasons. Some other interesting notes: - Goal=150: Set=(1...100), there are 19,378,091 subsets that sum to 150 (94 seconds to compute)

trinovantes 5y ago
Are you using 32/64 bit integers or arbitrary length inputs? It's NP-Complete because all of the known solutions are exponential to the number of bits of the input.
- zzxxyyaabbcc 5y ago
  The standard 4 byte int, on a 64x build
  - trinovantes 5y ago
    Then you did not solve the problem in polynomial time. Your runtime is probably (2^n)^C where n is the number of bits in the input and C is some constant.
gus_massa 5y ago
That the general problem is NP-complete does not mean that it's difficult to solve all the possible inputs. Sometimes to get a long run time, you need to construct an evil example on purpose. For example, if you have 1000 slots for numbers, make 3 of them with the last digit equal to 1, and the rest with the last digit equal to 0, and the expected sum a number where the last digit is 1. In this case, it's equivalent to asking that the algorithm choose exactly one of the slots with a number where the last digit is 1. Now do something similar with the second to last digit. And now with the third to last... You can select a lot of sets of 3 slots of the 1000 slots, and use this encoding to force the algorithm to choose exactly one in each one. The problem is that you need a lot of digits to use this encoding. But you are selecting numbers with 4 bytes, so you have only like 10 digits. With a better encoding, you can get like 16 conditions. How nasty can be an example with only number of 4 bytes? I'm not sure, but I think they are nos nasty enough. You should look for examples that are constructed on purpose to be difficult to solve. (I tried googling one, but I failed.) > Some other interesting notes: - Goal=150: Set=(1...100), there are 19,378,091 subsets that sum to 150 (94 seconds to compute) When the goal is small enough, there are some dynamic programing trics that are very fast. https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... The problem is difficult to solve when the number is huge and the sum is also huge.
zzxxyyaabbcc 5y ago
Because this is a new account Im nearly frozen from replying. I have updated the algorithm so that the RAM space is a bit over the size of the set. This also drastically cut down on computation time. E.g. A set of 200 integers takes 2MB of RAM. I used a 1+2+...+200 set for testing (since it is known to have tons of solutions) with a goal of 1000. Im at 360,000,000 solutions found 10 minutes into executing. The best existing algorithms out there can only handle 50-100 integers according to the wikipedia page. Basically, the time complexity of this algorithm is (roughly) limited to the number of possible solutions. If that's what makes the subset problem NP-Complete, then I guess I didnt solve anything, other than eliminating most of the fat in all the existing solutions. >Your runtime is probably (2^n)^C where n is the number of bits in the input and C is some constant. If n is the set of all the numbers, then I would not have been able to create a 2^(80*4*8) solution in my lifetime (ref: paste bin). If n is the number of bits in an int 2^(4*8), how would that explain the time it took to calculate the solutions in the paste bin link? I dont have a traditional CS education gus_massa: I will try more complicated sets. I also couldnt find any existing sets to test against. A set of 1000 numbers is an order of magnitude higher than the best algorithms out there. If there are a lot of solutions in that set, then it will take a long, long time even with my algorithm.

3 points by zzxxyyaabbcc 5y ago

trinovantes 5y ago

Are you using 32/64 bit integers or arbitrary length inputs? It's NP-Complete because all of the known solutions are exponential to the number of bits of the input.

zzxxyyaabbcc 5y ago
The standard 4 byte int, on a 64x build
- trinovantes 5y ago
  Then you did not solve the problem in polynomial time. Your runtime is probably (2^n)^C where n is the number of bits in the input and C is some constant.

gus_massa 5y ago

That the general problem is NP-complete does not mean that it's difficult to solve all the possible inputs. Sometimes to get a long run time, you need to construct an evil example on purpose. For example, if you have 1000 slots for numbers, make 3 of them with the last digit equal to 1, and the rest with the last digit equal to 0, and the expected sum a number where the last digit is 1. In this case, it's equivalent to asking that the algorithm choose exactly one of the slots with a number where the last digit is 1. Now do something similar with the second to last digit. And now with the third to last... You can select a lot of sets of 3 slots of the 1000 slots, and use this encoding to force the algorithm to choose exactly one in each one. The problem is that you need a lot of digits to use this encoding. But you are selecting numbers with 4 bytes, so you have only like 10 digits. With a better encoding, you can get like 16 conditions. How nasty can be an example with only number of 4 bytes? I'm not sure, but I think they are nos nasty enough. You should look for examples that are constructed on purpose to be difficult to solve. (I tried googling one, but I failed.) > Some other interesting notes: - Goal=150: Set=(1...100), there are 19,378,091 subsets that sum to 150 (94 seconds to compute) When the goal is small enough, there are some dynamic programing trics that are very fast. https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... The problem is difficult to solve when the number is huge and the sum is also huge.

zzxxyyaabbcc 5y ago

Because this is a new account Im nearly frozen from replying. I have updated the algorithm so that the RAM space is a bit over the size of the set. This also drastically cut down on computation time. E.g. A set of 200 integers takes 2MB of RAM. I used a 1+2+...+200 set for testing (since it is known to have tons of solutions) with a goal of 1000. Im at 360,000,000 solutions found 10 minutes into executing. The best existing algorithms out there can only handle 50-100 integers according to the wikipedia page. Basically, the time complexity of this algorithm is (roughly) limited to the number of possible solutions. If that's what makes the subset problem NP-Complete, then I guess I didnt solve anything, other than eliminating most of the fat in all the existing solutions. >Your runtime is probably (2^n)^C where n is the number of bits in the input and C is some constant. If n is the set of all the numbers, then I would not have been able to create a 2^(80*4*8) solution in my lifetime (ref: paste bin). If n is the number of bits in an int 2^(4*8), how would that explain the time it took to calculate the solutions in the paste bin link? I dont have a traditional CS education gus_massa: I will try more complicated sets. I also couldnt find any existing sets to test against. A set of 1000 numbers is an order of magnitude higher than the best algorithms out there. If there are a lot of solutions in that set, then it will take a long, long time even with my algorithm.