4 ms·

Faster Space-Efficient Algorithms for Subset Sum, K-Sum and Related Problems

91 points by kushti 10y ago

nerdponx 10y ago
How much better is this than prior art?
- bradleyjg 10y ago
  In pure time terms it is worse, as the best prior was O$(2^.5n). However, that algorithm took O$(2^.25n) space. This algorithm uses only polynomial space but runs in O$(2^.86n) time. The naive solution runs in O$(2^n) and polynomial space. I believe this top line result will mostly be of interest to Computer Scientists, as a practical matter these problems are rarely solved exactly because even the fast algorithms are far too slow for non-trivial problem sizes. However, this part regarding the "list disjointment problem" may be of wider interest: "Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n^2) time algorithm if no value occurs too often in the same list." N.B. The HN parser won't let me use stars, so read star for each of the dollar signs in the first paragraph.
  - the8472 10y ago
    you could use the multiplication sign × or the middle dot ·
    - IanCal 10y ago
      The star here is not a multiplication. A bit more info on O star http://math.stackexchange.com/questions/672281/what-is-the-difference-between-the-big-o-and-big-o-star-asterisk-operator http://math.stackexchange.com/questions/672281/what-is-the-d...
      - the8472 10y ago
        Ah well, then there's the mathematical asterisk operator O∗ (U+2217) which is separate from the ascii asterisk O* and you could also use the "combining asterisk above" O ⃰ (O, whitespace, combining char) although that's probably abuse of the characters. The rules say > Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace. But apparently noen of the zero-width spaces are not counted as whitespace.
- jsc 10y ago
  This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
  - AstralStorm 10y ago
    Apples, oranges. We have heuristic algorithms for knapsack running in polynomial time. The trick is that because they are heuristic, they do not necessarily solve the problem.
cschmidt 10y ago
Subset sum is NP-complete (https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem), so wouldn't this imply that P = NP? Hence, I don't believe it.
- aklein 10y ago
  My interpretation is: it's exponential in running time, although slightly faster than 2^n (exponent specifically is 0.86n). However, it uses polynomial space, which hadn't been done before. Prior approaches used an exponential-size lookup table. So there is no implication of P=NP.
- deleted 10y ago
  [deleted]
- kenoph 10y ago
  They don't solve it in polynomial time.
- cschmidt 10y ago
  Sorry, looking at the paper, they aren't claiming a polynomial time solution, so I retract my previous comment. They just claim "faster" than previous, but still exponential. The previous best was O(2^(n/2)) time and O(2^(n/4)) space, which they improve to O*(2^(0.86n)) time and polynomial space.
  - vanderZwan 10y ago
    I must be missing something obvious, but how is 0.86n better than n/2 and n/4? EDIT: I just noticed the space/polynomial space distinction, so I guess that's the improvement, but I don't know what that means.
    - timtadh 10y ago
      From a purely practical standpoint it means it is more tractable to solve large instances exactly. You can always wait for an answer but if you need more memory than you have you are out of luck. For instance, let's say before you had a problem of size 64. 2^64 bytes in gigabytes is 10^10 gigabytes. That is more ram than I have. However, a constant multiple (say 1,000,000,000) gives only 64 gigabytes. That takes an intractable problem to a tractable problem on a server with a large amount of memory. Yes, you still have to wait for the solution (maybe a long time) but at least you would have a hope of actually solving it.

91 points by kushti 10y ago

nerdponx 10y ago

How much better is this than prior art?

bradleyjg 10y ago
In pure time terms it is worse, as the best prior was O$(2^.5n). However, that algorithm took O$(2^.25n) space. This algorithm uses only polynomial space but runs in O$(2^.86n) time. The naive solution runs in O$(2^n) and polynomial space. I believe this top line result will mostly be of interest to Computer Scientists, as a practical matter these problems are rarely solved exactly because even the fast algorithms are far too slow for non-trivial problem sizes. However, this part regarding the "list disjointment problem" may be of wider interest: "Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n^2) time algorithm if no value occurs too often in the same list." N.B. The HN parser won't let me use stars, so read star for each of the dollar signs in the first paragraph.
- the8472 10y ago
  you could use the multiplication sign × or the middle dot ·
  - IanCal 10y ago
    The star here is not a multiplication. A bit more info on O star http://math.stackexchange.com/questions/672281/what-is-the-difference-between-the-big-o-and-big-o-star-asterisk-operator http://math.stackexchange.com/questions/672281/what-is-the-d...
    - the8472 10y ago
      Ah well, then there's the mathematical asterisk operator O∗ (U+2217) which is separate from the ascii asterisk O* and you could also use the "combining asterisk above" O ⃰ (O, whitespace, combining char) although that's probably abuse of the characters. The rules say > Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace. But apparently noen of the zero-width spaces are not counted as whitespace.
jsc 10y ago
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
- AstralStorm 10y ago
  Apples, oranges. We have heuristic algorithms for knapsack running in polynomial time. The trick is that because they are heuristic, they do not necessarily solve the problem.

cschmidt 10y ago

Subset sum is NP-complete (https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem), so wouldn't this imply that P = NP? Hence, I don't believe it.

aklein 10y ago
My interpretation is: it's exponential in running time, although slightly faster than 2^n (exponent specifically is 0.86n). However, it uses polynomial space, which hadn't been done before. Prior approaches used an exponential-size lookup table. So there is no implication of P=NP.
deleted 10y ago
[deleted]
kenoph 10y ago
They don't solve it in polynomial time.
cschmidt 10y ago
Sorry, looking at the paper, they aren't claiming a polynomial time solution, so I retract my previous comment. They just claim "faster" than previous, but still exponential. The previous best was O(2^(n/2)) time and O(2^(n/4)) space, which they improve to O*(2^(0.86n)) time and polynomial space.
- vanderZwan 10y ago
  I must be missing something obvious, but how is 0.86n better than n/2 and n/4? EDIT: I just noticed the space/polynomial space distinction, so I guess that's the improvement, but I don't know what that means.
  - timtadh 10y ago
    From a purely practical standpoint it means it is more tractable to solve large instances exactly. You can always wait for an answer but if you need more memory than you have you are out of luck. For instance, let's say before you had a problem of size 64. 2^64 bytes in gigabytes is 10^10 gigabytes. That is more ram than I have. However, a constant multiple (say 1,000,000,000) gives only 64 gigabytes. That takes an intractable problem to a tractable problem on a server with a large amount of memory. Yes, you still have to wait for the solution (maybe a long time) but at least you would have a hope of actually solving it.