3
$\begingroup$

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?

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ we've already been over this here: cstheory.stackexchange.com/questions/9184/…. your lower bound arguments are invalid $\endgroup$
    – Sasho Nikolov
    Jun 13, 2013 at 16:59
  • 2
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Jun 14, 2013 at 2:56
  • 2
    $\begingroup$ @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 Computer Science. 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. $\endgroup$
    – Kaveh
    Jun 14, 2013 at 2:56
  • 2
    $\begingroup$ Did you read my comments? If you continue to use cstheory to promote and discuss your ideas your account will be suspended. I would advise you to take this warning seriously. $\endgroup$
    – Kaveh
    Jun 14, 2013 at 14:42
  • 1
    $\begingroup$ You have violated the policy about discussing unpublished preprints by posting your answer which is essentially this. I am not going to repeat the warning. $\endgroup$
    – Kaveh
    Jun 14, 2013 at 15:54

2 Answers 2

Reset to default
9
$\begingroup$

Maybe.

Becker, Coron, and Joux [EUROCRYPT 2011 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], 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.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ 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 arxiv.org/abs/1303.0609 that will be presented on this years ICALP. It is still a randomized algorithm though... $\endgroup$
    – Andreas Björklund
    Jun 12, 2013 at 20:06
  • $\begingroup$ 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. $\endgroup$
    – Jeffε
    Jun 12, 2013 at 20:59
-9
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Jun 14, 2013 at 0:20
  • 8
    $\begingroup$ 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. $\endgroup$
    – Andreas Björklund
    Jun 14, 2013 at 2:32
  • 3
    $\begingroup$ I think you have some basic misunderstandings, and you repeat them. 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. $\endgroup$
    – Kaveh
    Jun 14, 2013 at 2:50
  • 5
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    Jun 14, 2013 at 3:25
  • 5
    $\begingroup$ Moreover, you've repeated these arguments for many years. $\endgroup$
    – Jeffε
    Jun 14, 2013 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.