5 ms·

If it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time.

kachnuv_ocasek 11y ago
I'm not sure I understand what you're saying. The class of problems Babai's algorithm can solve is exactly the same as the problems any other of the algorithms can solve. They're all asymptotically bounded in time, as well.
- jsprogrammer 11y ago
  If you have a finite amount of time, a given algorithm will only be able to solve a subset of all problem instances in the allocated time (assuming an infinite set of problem instances). If you have two algorithms and give the same finite amount of time to each, the asymptotically faster one would be expected to be able to solve more and/or larger problem instances in the allocated time than the asymptotically slower algorithm, as your allocated time increases.
  - monochromatic 11y ago
    If the finite time is smallish, and the constant factor in the asymptotically faster algorithm is sufficiently large, it might be the case that it can't solve any instances of the problem in that time.
  - daveguy 11y ago
    It is important to note that big o notation is not a measure of "how fast will it take". It is not a measure of time at all, but a matter of how many discrete steps are required to solved the problem as a function of input size. Each step could take longer, which could effectively give it a longer run time. Solvability by the algorithm and the big O notation assumes unlimited time. They are all " theoretically solvable". The constant time and size of N would determine which implementation would be practically faster in a given situation. Lower asymptotic bounds algorithms are faster, given a sufficiently large (and specific) N. But that depends on the implementations. It may be that N is larger than most GI problems compared to the programs that currently run. The current algorithms run in polynomial time for most graphs (just like many sorting algorithms run closer to n rather than n log n the closer you get to pre-sorted input)
sweezyjeezy 11y ago
Yeah, but the question is does the new algorithm beat the old ones for problems that are solvable in reasonable time. A constant time algorithm is not that useful if the constant happens to be 10^1000 years.
- jsprogrammer 11y ago
  I don't think this claims to be a constant time algorithm. Can someone rule out that there are no problem instances that this algorithm can solve in a reasonable time that others cannot?
  - sweezyjeezy 11y ago
    Reread my comment, I'm not saying that it's a constant time algorithm, I'm saying that even constant time algorithms can be impractical.
    - jsprogrammer 11y ago
      Reread my comment.
  - mcherm 11y ago
    If the paper is correct then there ARE problems that this algorithm can solve in less time than others. But it may be that every problem on which it is faster requires more bits of memory than there are atoms in the universe. Or that every problem on which it is faster would have a runtime that is 10^100 times the lifetime of the universe.
    - jsprogrammer 11y ago
      Any of those things could be the case. I'd modify your second sentence to say known atoms in the universe, and the second: projected lifetime. Do you know if the paper (or any commentary) addresses these concerns?
j2kun 11y ago
The claims you're making in this subthread are not precise enough to be correct. If you only allow a constant finite amount of time to solve a given problem, then aysmptotics guarantee nothing. An O(1) time could solve fewer instances than an O(2^2^n) time algorithm. It is also not true that the asymptotically faster algorithm "can solve more instances as the allocated time increases." These statements are only true if you add the phrase "sufficiently large" to them. So asymptotically faster algorithms can solve more instances as the allocated time bound increases, provided that the time bound is sufficiently large. But how large that "sufficiently large" needs to be is arbitrary, so you can't say that Babai's algorithm is practical without either precisely studying the constants involved in the algorithm (which Babai did to some extent, but omitted in the notation for clarity), or doing empirical analysis, which is unlikely to ever happen with Babai's algorithm.
- jsprogrammer 11y ago
  The statement is correct. "Sufficiently large" is implied and also not strictly necessary for the statement to be correct.
  - j2kun 11y ago
    If it's not required then it's not implied, and unfortunately it is required. If you want to keep having serious discussions about this stuff I suggest you go read some more about algorithms.
    - jsprogrammer 11y ago
      You should be able to simply state the error in my statement then. Anyway, others disagree with you.
dragonwriter 11y ago
> If it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time. More precisely, there are problems that the asymptotically faster one can solve in less time than the asymptotically slower one, or, equivalently, there exists some time period at and beyond which the asymptotically faster algorithm can solve problems that cannot be solved by the asymptotically slower one in the same time. However, the minimum time period where that becomes true with real implementations running on real, available hardware may be very large, so there may not be any practical advantages to an asymptotically faster algorithm.
- jsprogrammer 11y ago
  Agreed. One would need to actually present actual implementations to compare.
fryguy 11y ago
It may not be the case in our universe. An O(n^2) algorithm is only faster than O(n^3) algorithm for an n > N (N may be 0). N may be so large that the problems it solves faster take more time than the heat death of the universe.

kachnuv_ocasek 11y ago

I'm not sure I understand what you're saying. The class of problems Babai's algorithm can solve is exactly the same as the problems any other of the algorithms can solve. They're all asymptotically bounded in time, as well.

jsprogrammer 11y ago
If you have a finite amount of time, a given algorithm will only be able to solve a subset of all problem instances in the allocated time (assuming an infinite set of problem instances). If you have two algorithms and give the same finite amount of time to each, the asymptotically faster one would be expected to be able to solve more and/or larger problem instances in the allocated time than the asymptotically slower algorithm, as your allocated time increases.
- monochromatic 11y ago
  If the finite time is smallish, and the constant factor in the asymptotically faster algorithm is sufficiently large, it might be the case that it can't solve any instances of the problem in that time.
- daveguy 11y ago
  It is important to note that big o notation is not a measure of "how fast will it take". It is not a measure of time at all, but a matter of how many discrete steps are required to solved the problem as a function of input size. Each step could take longer, which could effectively give it a longer run time. Solvability by the algorithm and the big O notation assumes unlimited time. They are all " theoretically solvable". The constant time and size of N would determine which implementation would be practically faster in a given situation. Lower asymptotic bounds algorithms are faster, given a sufficiently large (and specific) N. But that depends on the implementations. It may be that N is larger than most GI problems compared to the programs that currently run. The current algorithms run in polynomial time for most graphs (just like many sorting algorithms run closer to n rather than n log n the closer you get to pre-sorted input)

sweezyjeezy 11y ago

Yeah, but the question is does the new algorithm beat the old ones for problems that are solvable in reasonable time. A constant time algorithm is not that useful if the constant happens to be 10^1000 years.

jsprogrammer 11y ago
I don't think this claims to be a constant time algorithm. Can someone rule out that there are no problem instances that this algorithm can solve in a reasonable time that others cannot?
- sweezyjeezy 11y ago
  Reread my comment, I'm not saying that it's a constant time algorithm, I'm saying that even constant time algorithms can be impractical.
  - jsprogrammer 11y ago
    Reread my comment.
- mcherm 11y ago
  If the paper is correct then there ARE problems that this algorithm can solve in less time than others. But it may be that every problem on which it is faster requires more bits of memory than there are atoms in the universe. Or that every problem on which it is faster would have a runtime that is 10^100 times the lifetime of the universe.
  - jsprogrammer 11y ago
    Any of those things could be the case. I'd modify your second sentence to say known atoms in the universe, and the second: projected lifetime. Do you know if the paper (or any commentary) addresses these concerns?

j2kun 11y ago

The claims you're making in this subthread are not precise enough to be correct. If you only allow a constant finite amount of time to solve a given problem, then aysmptotics guarantee nothing. An O(1) time could solve fewer instances than an O(2^2^n) time algorithm. It is also not true that the asymptotically faster algorithm "can solve more instances as the allocated time increases." These statements are only true if you add the phrase "sufficiently large" to them. So asymptotically faster algorithms can solve more instances as the allocated time bound increases, provided that the time bound is sufficiently large. But how large that "sufficiently large" needs to be is arbitrary, so you can't say that Babai's algorithm is practical without either precisely studying the constants involved in the algorithm (which Babai did to some extent, but omitted in the notation for clarity), or doing empirical analysis, which is unlikely to ever happen with Babai's algorithm.

jsprogrammer 11y ago
The statement is correct. "Sufficiently large" is implied and also not strictly necessary for the statement to be correct.
- j2kun 11y ago
  If it's not required then it's not implied, and unfortunately it is required. If you want to keep having serious discussions about this stuff I suggest you go read some more about algorithms.
  - jsprogrammer 11y ago
    You should be able to simply state the error in my statement then. Anyway, others disagree with you.

dragonwriter 11y ago

> If it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time. More precisely, there are problems that the asymptotically faster one can solve in less time than the asymptotically slower one, or, equivalently, there exists some time period at and beyond which the asymptotically faster algorithm can solve problems that cannot be solved by the asymptotically slower one in the same time. However, the minimum time period where that becomes true with real implementations running on real, available hardware may be very large, so there may not be any practical advantages to an asymptotically faster algorithm.

jsprogrammer 11y ago
Agreed. One would need to actually present actual implementations to compare.

fryguy 11y ago

It may not be the case in our universe. An O(n^2) algorithm is only faster than O(n^3) algorithm for an n > N (N may be 0). N may be so large that the problems it solves faster take more time than the heat death of the universe.