<p>I have been working in a subset sum problem solver for some time.</p>

<p>The implementation is an exact/exhaustive search solver.</p>

<p>The variable determining the asymptomatic growth rate is just $N$ (the number of elements in the input).</p>

<p>Current upper bound is $O^{*}(2^{log(N)^{2}})$</p>

<p>$M$, the bit length of each input variable from the set, does not impact/change the asymptomatic growth rate, that is, it has the same upper bound for an input set with 32 elements/32 bits per value than an input set with 32 elements using 35,50,64 (or more bits) to represent the values.</p>

<p>By current implementation details this is true for  $N \leq 33$. Higher values of $N$ will require to continue developing the method a bit.</p>

<p>Giving the above information. </p>

<p>Do you think it worth continue developing this method or better look to improve the upper bound before going into additional work?</p>

CC BY-SA 3.0
2014-12-15T11:47:00.507Z
What am I reading wrong?: $O(2^{logN*logN})=O(N^{logN})$ right?  so this is a sub-exponential, exact algorithm for subset sum?
Harry
CC BY-SA 3.0
2014-12-15T18:05:34.460Z
@Harry no, you are not reading wrong, just I forget the * for the polynomial factors (sorry about this) I edited the question to reflect this. The accurate upper bound is $O(N^4+2^{log(N)^{2}})$ however as I said, right now, is limited to $N \leq 33$
John Flanders
CC BY-SA 3.0
2014-12-15T18:46:06.240Z
A quasipolynomial time algorithm for subset sum implies that all of NP can be solved in quasipolynomial time, and I consider that extremely unlikely. So I guess what I am saying is that if you can prove such a thing it would be a major result but I am apriori very skeptical that you can.
Sasho Nikolov
CC BY-SA 3.0
2014-12-15T22:26:54.250Z
@SashoNikolov I completely understand your skepticism. The method is not just 'magic' and the algorithm is already implemented and working. Although there is always a chance that the time analysis is somehow flawed and that will be my fault. I didn't want to open a discussion about how unlikely is this. Just raised a question that really matters me. You can treat the question context as hypothetical if you want.
John Flanders
CC BY-SA 3.0
2014-12-16T00:05:15.023Z
few algorithms are implemented in a way that complexity estimates apply for only some $N$ finite limit so that does not inspire confidence. also, the immediate question is where the algorithm fits into the spectrum of known/ published subset sum algorithms/ approaches which only you can answer at this time...
vzn
CC BY-SA 3.0
2014-12-16T18:08:07.407Z
@vzn Hi. I understand your concerns and questions, thanks for sharing. However,  right now, my concern is not get feedback from the community about feasibility/validity. The question raised is exactly what I wanted to discuss. We can set the question's context back in the hypothetical domain if this helps. Both possible paths of action are really tough and I'd like to know what others will do in this context.
John Flanders
CC BY-SA 3.0
2014-12-16T18:32:29.683Z
First it's hard to answer this question when parts of the setup verge on the absurd (for example it's meaningless to say that some asymptotic bound is "true" for small $N$, let alone to claim that an implementation can show this). Second, what even *is* the question? What do you mean by developing this method? If you are asking whether a $2^{\log^2 N}$ algorithm for an NP-hard problem is interesting, then 1) this is not research level question, 2) yes, it definitely is interesting.
Sasho Nikolov
CC BY-SA 3.0
2014-12-16T19:12:07.513Z
my answer to this is, dont attempt to do any research whatsoever without investigating prior approaches & basic bkg theory that is applicable. this seems so far to express no major awareness of prior research in the area. what is also likely is that youve miscalculated the complexity. complexity is generally not based on machine word bit-lengths, thats fundamental. (it is occasionally expressed in terms of operations on bitvectors however.)
vzn
CC BY-SA 4.0
2018-10-20T12:59:20.837Z
I found an online solver (http://solver.8iq.ru/) for this problem. Probably you can contact the author of this solution.
pahaz
<cc.complexity-theory><time-complexity><np-complete>
Subset sum solver. Worth continue working on this method?
John Flanders
# Subset sum solver. Worth continue working on this method?

(Asked by: username_0 on 2014-12-15)

I have been working in a subset sum problem solver for some time.

The implementation is an exact/exhaustive search solver.

The variable determining the asymptomatic growth rate is just $N$ (the number of elements in the input).

Current upper bound is $O^{\*}(2^{log(N)^{2}})$

$M$, the bit length of each input variable from the set, does not impact/change the asymptomatic growth rate, that is, it has the same upper bound for an input set with 32 elements/32 bits per value than an input set with 32 elements using 35,50,64 (or more bits) to represent the values.

By current implementation details this is true for $N \leq 33$. Higher values of $N$ will require to continue developing the method a bit.

Giving the above information.

Do you think it worth continue developing this method or better look to improve the upper bound before going into additional work?

**Tags:** cc.complexity-theory, time-complexity, np-complete
> **Comments:**
> **username_1**: What am I reading wrong?: $O(2^{logN*logN})=O(N^{logN})$ right?  so this is a sub-exponential, exact algorithm for subset sum?  
> **username_0**: @Harry no, you are not reading wrong, just I forget the * for the polynomial factors (sorry about this) I edited the question to reflect this. The accurate upper bound is $O(N^4+2^{log(N)^{2}})$ however as I said, right now, is limited to $N \leq 33$  
> **username_2**: A quasipolynomial time algorithm for subset sum implies that all of NP can be solved in quasipolynomial time, and I consider that extremely unlikely. So I guess what I am saying is that if you can prove such a thing it would be a major result but I am apriori very skeptical that you can.  
> **username_0**: @SashoNikolov I completely understand your skepticism. The method is not just 'magic' and the algorithm is already implemented and working. Although there is always a chance that the time analysis is somehow flawed and that will be my fault. I didn't want to open a discussion about how unlikely is this. Just raised a question that really matters me. You can treat the question context as hypothetical if you want.  
> **username_3**: few algorithms are implemented in a way that complexity estimates apply for only some $N$ finite limit so that does not inspire confidence. also, the immediate question is where the algorithm fits into the spectrum of known/ published subset sum algorithms/ approaches which only you can answer at this time...  
> **username_0**: @vzn Hi. I understand your concerns and questions, thanks for sharing. However,  right now, my concern is not get feedback from the community about feasibility/validity. The question raised is exactly what I wanted to discuss. We can set the question's context back in the hypothetical domain if this helps. Both possible paths of action are really tough and I'd like to know what others will do in this context.  
> **username_2**: First it's hard to answer this question when parts of the setup verge on the absurd (for example it's meaningless to say that some asymptotic bound is "true" for small $N$, let alone to claim that an implementation can show this). Second, what even *is* the question? What do you mean by developing this method? If you are asking whether a $2^{\log^2 N}$ algorithm for an NP-hard problem is interesting, then 1) this is not research level question, 2) yes, it definitely is interesting.  
> **username_3**: my answer to this is, dont attempt to do any research whatsoever without investigating prior approaches & basic bkg theory that is applicable. this seems so far to express no major awareness of prior research in the area. what is also likely is that youve miscalculated the complexity. complexity is generally not based on machine word bit-lengths, thats fundamental. (it is occasionally expressed in terms of operations on bitvectors however.)  
> **username_4**: I found an online solver (http://solver.8iq.ru/) for this problem. Probably you can contact the author of this solution.  

---

## 0 answers

