Hacker News Reader

Comment by raverbashing | Hacker News Reader

Ok so the question is, while theoretically this is an important work, is it really worthy having a practical implementation?

(I remember something similar happening with "Primality testing is P" but the existing, non-P algorithms were good enough so people wouldn't bother using it except in specific situations)

View on HN

No. As the author notes in the preprint, there are already numerous very fast, practical algorithms. This one is only asymptotically faster, and by itself it would probably be slower in real-world applications.

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.

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.

The statement is correct.

"Sufficiently large" is implied and also not strictly necessary for the statement to be correct.

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.

You should be able to simply state the error in my statement then. Anyway, others disagree with you.

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.

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?

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.

Reread my comment.

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.

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?

> 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.

Agreed. One would need to actually present actual implementations to compare.

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.

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.

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.

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)

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.

The algorithm is only of theoretical interest, the situation is similar to primality testing. In practice programs such as nauty are good enough.

He said in the talk, answering this exact question, that basically his result shows that there aren't any really hard cases for the heuristic algorithms to run into. It would of course require some analysis to connect them to his result, but there would be no point in implementing his algorithm on a computer.

Reply on news.ycombinator.com