Faster Space-Efficient Algorithms for Subset Sum, K-Sum and Related Problems(arxiv.org)
arxiv.org
Faster Space-Efficient Algorithms for Subset Sum, K-Sum and Related Problems
https://arxiv.org/abs/1612.02788
2 comments
How much better is this than prior art?
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.
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.
you could use the multiplication sign × or the middle dot ·
The star here is not a multiplication. A bit more info on O star http://math.stackexchange.com/questions/672281/what-is-the-d...
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.
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.
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
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.
Subset sum is NP-complete (https://en.wikipedia.org/wiki/Subset_sum_problem), so wouldn't this imply that P = NP? Hence, I don't believe it.
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.
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.
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.
EDIT: I just noticed the space/polynomial space distinction, so I guess that's the improvement, but I don't know what that means.
Complexity theory literature is littered with algorithms that rely on things like O(1) access to a 2^O(n)-sized array. They are almost uniformly wildly impractical. In fact, even 2^O(w) (where w is the word size in bits), which you see sometimes in the succinct data structures literature on stuff like optimal compression of bit vectors, is usually unusable because the asymptotic improvement doesn't kick in until w = 128 or whatever.
As another illustrative example, if you allow unbounded fan-in and an exponential number of AND/OR gates, you can solve any monotone boolean function in two steps (you just take the DNF of a positive input and turn it into a circuit). This means that if you're willing to use an unbounded amount of space (chip area, in this case), you can simulate things like k-clique for any fixed k < n in two steps. As a result, essentially all circuit lower bound results either restrict fanin (to 2, generally) or restrict you to polynomial chip area.
Moreover, you can encode any monotone boolean function of n inputs in O(lg(Dedekind(n))) bits as long as you have an auxiliary array of size O(Dedekind(n)), which you can look up answers in in constant time. So you can compress boolean functions pretty well (about 5x more than the naive bit lookup solution for n=32), but Dedekind(n) grows so fast that nobody would ever actually try to implement this.
I have lots more examples, if you want them :P Exponential space algorithms are almost totally useless in nearly all cases (with the exception of those that only rarely take exponential space).
As another illustrative example, if you allow unbounded fan-in and an exponential number of AND/OR gates, you can solve any monotone boolean function in two steps (you just take the DNF of a positive input and turn it into a circuit). This means that if you're willing to use an unbounded amount of space (chip area, in this case), you can simulate things like k-clique for any fixed k < n in two steps. As a result, essentially all circuit lower bound results either restrict fanin (to 2, generally) or restrict you to polynomial chip area.
Moreover, you can encode any monotone boolean function of n inputs in O(lg(Dedekind(n))) bits as long as you have an auxiliary array of size O(Dedekind(n)), which you can look up answers in in constant time. So you can compress boolean functions pretty well (about 5x more than the naive bit lookup solution for n=32), but Dedekind(n) grows so fast that nobody would ever actually try to implement this.
I have lots more examples, if you want them :P Exponential space algorithms are almost totally useless in nearly all cases (with the exception of those that only rarely take exponential space).
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.
> You can always wait for an answer but if you need more memory than you have you are out of luck.
I'm not a practical programmer, so I may be off base, but it seems to me that one could as well say "You can always buy more memory, but if the answer takes more time than you have to wait then you're out of luck." (In both cases, super-rapid growth won't take too long to exhaust the age, and the information capacity, of the universe.) Is it really clear that it's better to err on the side of more time in the time / space trade-off?
I'm not a practical programmer, so I may be off base, but it seems to me that one could as well say "You can always buy more memory, but if the answer takes more time than you have to wait then you're out of luck." (In both cases, super-rapid growth won't take too long to exhaust the age, and the information capacity, of the universe.) Is it really clear that it's better to err on the side of more time in the time / space trade-off?
No, because accessing memory also takes a lot of time. This is especially true on small machines like cellphones.
Time is how long it takes to run, which is based on how many operations you will use.
Space is how much memory you need to run it.
Frequently in operations there is a tradeoff between time and space. The classic example being that saving previous results in a lookup table requires more space but saves time because you eliminate repeat calculations.
We already had O(2^n) time with O(n) space, or O(2^(n/2)) time with O(2^(n/4)) space. This algorithm represents a new tradeoff between those two points.
Note that these are all worst case scenarios. In practice for sets of modest sized integers, subset sum is solvable in reasonable time and space. See https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... for details.
Space is how much memory you need to run it.
Frequently in operations there is a tradeoff between time and space. The classic example being that saving previous results in a lookup table requires more space but saves time because you eliminate repeat calculations.
We already had O(2^n) time with O(n) space, or O(2^(n/2)) time with O(2^(n/4)) space. This algorithm represents a new tradeoff between those two points.
Note that these are all worst case scenarios. In practice for sets of modest sized integers, subset sum is solvable in reasonable time and space. See https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... for details.
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.
It's still exponential ( O*(2^(0.86n)) ). If anything, it might show that Exponential Time Hypothesis is wrong, but I don't think it's the case here. (As far as I know there is no "constant keeping" reduction from subset sum to SAT).
They don't solve it in polynomial time.
[deleted]