2
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by Kristoffer Arnsfelt Hansen, R B, Sasho Nikolov, András Salamon, Lev Reyzin Dec 17 '14 at 16:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What am I reading wrong?: $O(2^{logN*logN})=O(N^{logN})$ right? so this is a sub-exponential, exact algorithm for subset sum? $\endgroup$ – Harry Dec 15 '14 at 11:47
  • 1
    $\begingroup$ @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$ $\endgroup$ – John Flanders Dec 15 '14 at 18:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 15 '14 at 18:46
  • 1
    $\begingroup$ @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. $\endgroup$ – John Flanders Dec 15 '14 at 22:26
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 16 '14 at 18:32