Hacker News
points by choeger 3 days ago | 0 comments
I am long out of this game, but the complexity class they show still has an n in the exponent, even if divided by log(n).

I have no intuition whatsoever on how that algorithm scales. Can anyone enlighten me?

[–] SkiFire13 2 days ago
The algorithm is still exponential, it just not in the class that the ETH claims. In practice it's likely worse than current algorithms for any reasonable input you might throw at it, and starts getting faster only once the problem is already too big.
[–] punty 2 days ago
2^(n/logn) will eventually be smaller than (1+epsilon)^n for any fixed positive epsilon. However, as log(n) grows quite slowly n will have to be exceptionally large. For epsilon=2^-D n will have to be something like 2^(2^D) large.
Hacker News