# new subset sum approach results

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $$O{n/2 \choose n/4}$$, demonstrating as well the hardest target value is not $$\approx \frac{sum(S)}{2}$$ but $$\approx\frac{sum(S)}{4}$$ for dense instances ($$d \approx 1$$) in all cases.

I asked several people about their opinion and I got mixed feedback, some people though it was worth it to keep pushing the approach before publishing (to try to obtain an improved result, given this is likely possible, then publish), while other people encouraged me to publish right away given the improvement over the $$O(2^{\frac{n}{2}})$$ approach and the new characterization for the hardest target values not demonstrated before in the available literature, then continue working looking to improve these results.

• What is TC? ${}$ – Emil Jeřábek Jan 10 at 10:08
• I don't have an answer to your question but personally I do find such a result interesting. For curious readers you can use Stirling's approximation to get $O({n/2 \choose n/4})$ $= O(\frac{2^{n/2}}{n})$, which imo provides a nicer comparison to the previous best algorithm – Phylliida Jan 10 at 15:37
• @Phylliida Wouldn't that be $O(2^{n/2}/\sqrt{n})$? – Clement C. Jan 11 at 3:17