3 ms·

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 sti

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.
  - JadeNB 10y ago
    > 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?
    - AstralStorm 10y ago
      No, because accessing memory also takes a lot of time. This is especially true on small machines like cellphones.
- btilly 10y ago
  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-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... for details.
- Jweb_Guru 10y ago
  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).

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.
- JadeNB 10y ago
  > 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?
  - AstralStorm 10y ago
    No, because accessing memory also takes a lot of time. This is especially true on small machines like cellphones.
btilly 10y ago
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-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... for details.
Jweb_Guru 10y ago
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).