Let assume there is way to apply a divide & conquer approach to the classical subset sum solver of Horowitz and Sahni.

And for this, we design a decomposition function, when applied to the algorithm changes the dynamics from solving 1 single problem to no more than $n$ sub-problems. ($n = |S|$, $S$ = input instance)

The algorithm will iterate solving the sub-problems one after the other, combining its results, and no sub-problem will be worse than $\widetilde{O}(2^{n/2.36})$ (assume the combining function is negligible).

The algorithm, when run to completion, has executed an exhaustive search, and when the process ends, all subsets from $S$ have been verified, emitting the subset adding up to $t$ (t=target value) if exists.

Assuming we are talking about processing 'hard' instances, would be this good enough to prove an exact algorithm with a better Time Complexity than the classical is possible?

  • 3
    $\begingroup$ Suppose it partitions S into two subsets A and B of size n-1 and 1, respectively, then takes $\tilde \Theta(2^{|A|/2.36})$ time to solve $A$. Then the entire computation takes time at least $\tilde \Omega(2^{(n-1)/2.36}) = \tilde \Omega(2^{n/2.36})$. Is that better than "classically possible"? $\endgroup$
    – Neal Young
    Oct 31, 2021 at 12:41
  • $\begingroup$ @JesusSalas, I'm not sure how to interpret your comment. Maybe my own comment above wasn't clear. My intention was to point out that the approach suggested in the post seems, in the worst case, to have the same asymptotic complexity as just taking whatever subroutine is used to solve the subproblems, and instead applying that subroutine directly to the given instance. But maybe I'm misunderstanding the post. $\endgroup$
    – Neal Young
    Oct 31, 2021 at 19:17
  • $\begingroup$ @NealYoung Sorry, I misunderstood the comment $\endgroup$ Oct 31, 2021 at 20:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.