<p>Let assume there is way to apply a divide &amp; conquer approach to the classical subset sum solver of Horowitz and Sahni.</p>
<p>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 <span class="math-container">$n$</span> sub-problems. (<span class="math-container">$n = |S|$</span>, <span class="math-container">$S$</span> = input instance)</p>
<p>The algorithm will iterate solving the sub-problems one after the other, combining its results, and no sub-problem will be worse than <span class="math-container">$\widetilde{O}(2^{n/2.36})$</span> (assume the combining function is negligible).</p>
<p>The algorithm, when run to completion, has executed an exhaustive search, and when the process ends, all subsets from <span class="math-container">$S$</span> have been verified, emitting the subset adding up to <span class="math-container">$t$</span> (t=target value) if exists.</p>
<p>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?</p>

CC BY-SA 4.0
2021-10-31T12:41:17.077Z
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"?
Neal Young
CC BY-SA 4.0
2021-10-31T19:17:52.537Z
@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.
Neal Young
CC BY-SA 4.0
2021-10-31T20:58:39.787Z
@NealYoung Sorry, I misunderstood the comment
Jesus Salas
<np-hardness><time-complexity>
Subset Sum Problem exact Algorithm (hypothetical)
John Seppard
# Subset Sum Problem exact Algorithm (hypothetical)

(Asked by: username_0 on 2021-10-28)

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?

**Tags:** np-hardness, time-complexity

> **Comments:**
> **username_1**: 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"?  
> **username_1**: @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.  
> **username_2**: @NealYoung Sorry, I misunderstood the comment  

---

## 0 answers

