<p><strong>Maybe.</strong></p>

<p>Becker, Coron, and Joux [<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-20465-4_21">EUROCRYPT 2011</a> describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981].  (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)</p>

<p>More recently, Dinur, Dunkelman, Keller, and Shamir [<a href="http://eprint.iacr.org/2012/217">Crypto 2012</a>], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack.  Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.</p>

<p>It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.</p>

CC BY-SA 3.0
2013-06-12T20:06:19.773Z
Aren't these results for *random* hard instances? My interpretation of the OP's question was that it asked for worst case results. As it happens, it doesn't matter for the latter result, see http://arxiv.org/abs/1303.0609 that will be presented on this years ICALP. It is still a randomized algorithm though...
Andreas Björklund
CC BY-SA 3.0
2013-06-12T20:59:54.280Z
Yes, you're right about random hard instances; that's a crucial limitation.  You're also right about the new algorithm being randomized, but whatever.
Jeffε
CC BY-SA 3.0
2013-06-12T18:27:59.700Z
2013-06-12T21:00:30.470Z
2013-06-12T21:00:30.470Z
Jeffε
<p>When I posted the question, I thought there might be an algorithm, but now I think the answer is no. </p>

<p>If it were possible to solve this problem in <span class="math-container">$o(3^{n/2})$</span> time in the worst-case scenario via a deterministic algorithm, it would be possible to manipulate the equation <span class="math-container">$\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$</span> so that there are <span class="math-container">$L$</span> possible expressions on the left-hand-side and <span class="math-container">$R$</span> possible expressions on the right-hand-side, where <span class="math-container">$L+R=o(3^{n/2})$</span>. But this appears to be impossible. </p>

<p>The best you can do is manipulate the equation to get <span class="math-container">$\Theta(3^{n/2})$</span> possible expressions on the left-hand-side and get <span class="math-container">$\Theta(3^{n/2})$</span> possible expressions on the right-hand-side, as follows:</p>

<p><span class="math-container">$\sum_{i \in I^+}s_i - \sum_{j \in J^+} s_j=t-(\sum_{i \in I^-}s_i - \sum_{j \in J^-} s_j)$</span>, </p>

<p>where <span class="math-container">$I^+ =\{1,\dots,[n/2]\} \cap I$</span>, <span class="math-container">$I^- =\{[n/2]+1,\dots,n\} \cap I$</span>, <span class="math-container">$J^+ =\{1,\dots,[n/2]\} \cap J$</span>, and <span class="math-container">$J^- =\{[n/2]+1,\dots,n\} \cap J$</span>. This allows one to apply the Meet-in-the-Middle algorithm. I don't think anyone will find any algorithm that beats the Meet-in-the-Middle for this problem.</p>

<p>Added in 2019: this paper came out, which gives a probabilistic algorithm and also has a better name for the problem, "equal subset-sum".  <a href="https://arxiv.org/abs/1905.02424" rel="nofollow noreferrer">https://arxiv.org/abs/1905.02424</a></p>

CC BY-SA 3.0
2013-06-14T00:20:00.993Z
Read the papers cited in my answer.  Your objection applies to their problems as well, but they bypass your claimed barrier.  You are assuming a very restricted model of computation. A Turing machine does not have to "look at" _any_ sub expressions on either "side" of the equation.
Jeffε
CC BY-SA 3.0
2013-06-14T02:26:43.510Z
I don't think the algorithms in the paper that you cited are always successful in distinguishing between instances with a solution and instances with no solution. I don't understand your other objection.
Craig Feinstein
CC BY-SA 3.0
2013-06-14T02:29:08.363Z
I'm assuming a Turing machine model of computation.
Craig Feinstein
CC BY-SA 3.0
2013-06-14T02:32:20.580Z
Your argument also covers the case when the $s_i$ and $t$ instead of integers are elements of a finite field of characteristic two. But in this case we know a polynomial time algorithm, namely Gaussian elimination with the field elements viewed as $0/1$-vectors. So the underlying ring seems to matter for the computational complexity of Subset Sum and friends. Any hardness proof needs to at least address this issue.
Andreas Björklund
CC BY-SA 3.0
2013-06-14T02:50:56.043Z
I think you have some basic misunderstandings, and you repeat [them](http://cstheory.stackexchange.com/a/9281/). Your misunderstandings are undergraduate level and clarifying them is not on-topic for cstheory. If you continue to use cstheory as a discussion forum for your intuitions/ideas you will be suspended.
Kaveh
CC BY-SA 3.0
2013-06-14T03:25:28.663Z
ps: let me try to explain the fundamental problem with your argument (only for this time): the steps in your argument do not follow from the previous steps. This is a common issue with students when they start to learn serious mathematics. It is a common mistake to assume that something is true because we can't think of any situation where it is false. That is not a mathematically valid step. Therefore your argument is invalid (even if there is no such algorithm).
Kaveh
CC BY-SA 3.0
2013-06-14T03:50:31.897Z
Moreover, you've repeated these arguments for [many years](http://arxiv.org/abs/cs/0607093).
Jeffε
CC BY-SA 3.0
2013-06-14T11:17:34.410Z
@JeffE, You may not agree with my arguments, but my conclusions have never been contradicted and never will be contradicted. :-)
Craig Feinstein
CC BY-SA 4.0
2013-06-13T14:02:13.200Z
2019-05-24T23:33:35.640Z
2019-05-24T23:33:35.640Z
Craig Feinstein
<p>Consider the following problem:</p>

<p>SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$.</p>

<p>The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?</p>

CC BY-SA 3.0
2013-06-13T11:12:16.243Z
When I asked the question, I thought that the answer is yes. Now, I am positive that the answer is no.
Craig Feinstein
CC BY-SA 3.0
2013-06-13T16:59:02.960Z
we've already been over this here: http://cstheory.stackexchange.com/questions/9184/computing-the-mobius-function/9281#9281. your lower bound arguments are invalid
Sasho Nikolov
CC BY-SA 3.0
2013-06-13T17:11:27.593Z
@Sasho Nikolov, Do you know an algorithm that runs in $o(3^{n/2})$ time?
Craig Feinstein
CC BY-SA 3.0
2013-06-14T02:30:52.483Z
It seems to me this is not a real question. I am voting to close as not a real question.
Kaveh
CC BY-SA 3.0
2013-06-14T02:53:21.200Z
@Kaveh: I don't think there is anything wrong with the question in itself. A lot of researchers I know including myself invest serious time thinking about related questions in the hope of bypassing such apparent barriers.
Andreas Björklund
CC BY-SA 3.0
2013-06-14T02:56:09.410Z
@Andreas, I don't think the question is problematic by itself. It is a fine question. The reason I am saying it is not a real question is because it seems to me that the OP is using these questions to express his own ideas, i.e. asking a question doesn't seem to be the real intention.
Kaveh
CC BY-SA 3.0
2013-06-14T02:56:58.223Z
@Craig, one does not need such an algorithm to see that a lower-bound argument is invalid. If you don't understand this I suggest that you ask for an explanation on [cs.se]. ps: IMO, before asking and thinking about these questions you should acquire some basic mathematical maturity because you don't seem to understand what we tell you.
Kaveh
CC BY-SA 3.0
2013-06-14T11:05:26.973Z
@Kaveh, the real intention of my question was to get the answer, like all of my questions. Do you know the answer?
Craig Feinstein
CC BY-SA 3.0
2013-06-14T14:42:53.460Z
Did you read my comments? If you continue to use cstheory to promote and discuss [your ideas](http://arxiv.org/abs/cs/0607093) your account will be suspended. I would advise you to take this warning seriously.
Kaveh
CC BY-SA 3.0
2013-06-14T15:32:26.370Z
@Kaveh, if I have broken any rules of this forum by asking and answering my own question, then by all means suspend my account.
Craig Feinstein
CC BY-SA 3.0
2013-06-14T15:54:01.953Z
You have violated [the policy about discussing unpublished preprints](http://meta.cstheory.stackexchange.com/q/274) by posting your answer which is essentially [this](http://arxiv.org/abs/cs/0607093). I am not going to repeat the warning.
Kaveh
CC BY-SA 3.0
2013-06-14T16:05:44.687Z
@Kaveh, then do the right thing, according to the rules of this forum.
Craig Feinstein
CC BY-SA 3.0
2013-06-14T17:01:30.403Z
The preprint that you cited has been published.
Craig Feinstein
<ds.algorithms>
Subset-sum-difference problem
Craig Feinstein
# Subset-sum-difference problem

(Asked by: username_0 on 2013-06-12)

Consider the following problem:

SUBSET-SUM-DIFFERENCE: Let $S=\{s\_1,\dots,s\_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum\_{i \in I}s\_i - \sum\_{j \in J} s\_j=t$.

The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?

**Tags:** ds.algorithms
> **Comments:**
> **username_0**: When I asked the question, I thought that the answer is yes. Now, I am positive that the answer is no.  
> **username_1**: we've already been over this here: http://cstheory.stackexchange.com/questions/9184/computing-the-mobius-function/9281#9281. your lower bound arguments are invalid  
> **username_0**: @Sasho Nikolov, Do you know an algorithm that runs in $o(3^{n/2})$ time?  
> **username_2**: It seems to me this is not a real question. I am voting to close as not a real question.  
> **username_3**: @Kaveh: I don't think there is anything wrong with the question in itself. A lot of researchers I know including myself invest serious time thinking about related questions in the hope of bypassing such apparent barriers.  
> **username_2**: @Andreas, I don't think the question is problematic by itself. It is a fine question. The reason I am saying it is not a real question is because it seems to me that the OP is using these questions to express his own ideas, i.e. asking a question doesn't seem to be the real intention.  
> **username_2**: @Craig, one does not need such an algorithm to see that a lower-bound argument is invalid. If you don't understand this I suggest that you ask for an explanation on [cs.se]. ps: IMO, before asking and thinking about these questions you should acquire some basic mathematical maturity because you don't seem to understand what we tell you.  
> **username_0**: @Kaveh, the real intention of my question was to get the answer, like all of my questions. Do you know the answer?  
> **username_2**: Did you read my comments? If you continue to use cstheory to promote and discuss [your ideas](http://arxiv.org/abs/cs/0607093) your account will be suspended. I would advise you to take this warning seriously.  
> **username_0**: @Kaveh, if I have broken any rules of this forum by asking and answering my own question, then by all means suspend my account.  
> **username_2**: You have violated [the policy about discussing unpublished preprints](http://meta.cstheory.stackexchange.com/q/274) by posting your answer which is essentially [this](http://arxiv.org/abs/cs/0607093). I am not going to repeat the warning.  
> **username_0**: @Kaveh, then do the right thing, according to the rules of this forum.  
> **username_0**: The preprint that you cited has been published.  

---

## 2 answers

### Answer by username_4 on 2013-06-12. Score: 9

**Maybe.**

Becker, Coron, and Joux [[EUROCRYPT 2011](http://link.springer.com/chapter/10.1007%2F978-3-642-20465-4_21) describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981]. (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)

More recently, Dinur, Dunkelman, Keller, and Shamir [[Crypto 2012](http://eprint.iacr.org/2012/217)], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack. Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.

It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.

> **Comments:**
> **username_3**: Aren't these results for *random* hard instances? My interpretation of the OP's question was that it asked for worst case results. As it happens, it doesn't matter for the latter result, see http://arxiv.org/abs/1303.0609 that will be presented on this years ICALP. It is still a randomized algorithm though...  
> **username_4**: Yes, you're right about random hard instances; that's a crucial limitation.  You're also right about the new algorithm being randomized, but whatever.  

---

### Answer by username_0 on 2013-06-13. Score: -9

When I posted the question, I thought there might be an algorithm, but now I think the answer is no.

If it were possible to solve this problem in $o(3^{n/2})$ time in the worst-case scenario via a deterministic algorithm, it would be possible to manipulate the equation $\sum\_{i \in I}s\_i - \sum\_{j \in J} s\_j=t$ so that there are $L$ possible expressions on the left-hand-side and $R$ possible expressions on the right-hand-side, where $L+R=o(3^{n/2})$. But this appears to be impossible.

The best you can do is manipulate the equation to get $\Theta(3^{n/2})$ possible expressions on the left-hand-side and get $\Theta(3^{n/2})$ possible expressions on the right-hand-side, as follows:

$\sum\_{i \in I^+}s\_i - \sum\_{j \in J^+} s\_j=t-(\sum\_{i \in I^-}s\_i - \sum\_{j \in J^-} s\_j)$,

where $I^+ =\{1,\dots,[n/2]\} \cap I$, $I^- =\{[n/2]+1,\dots,n\} \cap I$, $J^+ =\{1,\dots,[n/2]\} \cap J$, and $J^- =\{[n/2]+1,\dots,n\} \cap J$. This allows one to apply the Meet-in-the-Middle algorithm. I don't think anyone will find any algorithm that beats the Meet-in-the-Middle for this problem.

Added in 2019: this paper came out, which gives a probabilistic algorithm and also has a better name for the problem, "equal subset-sum". <https://arxiv.org/abs/1905.02424>

> **Comments:**
> **username_4**: Read the papers cited in my answer.  Your objection applies to their problems as well, but they bypass your claimed barrier.  You are assuming a very restricted model of computation. A Turing machine does not have to "look at" _any_ sub expressions on either "side" of the equation.  
> **username_0**: I don't think the algorithms in the paper that you cited are always successful in distinguishing between instances with a solution and instances with no solution. I don't understand your other objection.  
> **username_0**: I'm assuming a Turing machine model of computation.  
> **username_3**: Your argument also covers the case when the $s_i$ and $t$ instead of integers are elements of a finite field of characteristic two. But in this case we know a polynomial time algorithm, namely Gaussian elimination with the field elements viewed as $0/1$-vectors. So the underlying ring seems to matter for the computational complexity of Subset Sum and friends. Any hardness proof needs to at least address this issue.  
> **username_2**: I think you have some basic misunderstandings, and you repeat [them](http://cstheory.stackexchange.com/a/9281/). Your misunderstandings are undergraduate level and clarifying them is not on-topic for cstheory. If you continue to use cstheory as a discussion forum for your intuitions/ideas you will be suspended.  
> **username_2**: ps: let me try to explain the fundamental problem with your argument (only for this time): the steps in your argument do not follow from the previous steps. This is a common issue with students when they start to learn serious mathematics. It is a common mistake to assume that something is true because we can't think of any situation where it is false. That is not a mathematically valid step. Therefore your argument is invalid (even if there is no such algorithm).  
> **username_4**: Moreover, you've repeated these arguments for [many years](http://arxiv.org/abs/cs/0607093).  
> **username_0**: @JeffE, You may not agree with my arguments, but my conclusions have never been contradicted and never will be contradicted. :-)  

---

