Hacker News Reader

Comment by thomasahle | Hacker News Reader

It's interesting how nearly all algorithmic asymptotic running times can be specified just in terms of exp, log and powering. exp(exp(sqrt(log n)))=exp(exp(exp(log(log n)/2))) is a beautiful thing. But how comes we so rarely encounter other functions? Clearly this class doesn't cover everything we might need. Where are the exp(exp(a^(-1)(n))) algorithms, where a^(-1) is the inverse ackerman function?

View on HN

The iterated logarithm, a very slow-growing function, shows up naturally in algorithm analysis: https://en.wikipedia.org/wiki/Iterated_logarithm. And the inverse Ackermann of course shows up in union-find.

It's also worth pointing out that these functions sometimes turn up just in terms of the bounds that have been proven about algorithms -- the functions we see can reflect the kinds of analysis we can do of algorithms as much as the performance of the algorithms themselves.

And we also see some very weird exponents -- the best asymptotic bound we have on a matrix multiplication algorithm is n^2.3728639.

There are some such algorithms. You don't encounter them as often because we are biased towards encountering algorithms that can be implemented efficiently or at least can be approximated efficiently (i.e., a great many "NP-complete" problems admit of usable approximation algorithms with varying degrees of usability).

Plus, in perhaps a bit deeper philosophical sense, we are ourselves biased towards expressing problems that have relatively simple complexities as their solution. While there are some simple problem that have complicated optimal solutions, certainly, I'd say that in general the vast bulk of problems for which the optimal solution has Ackermann's complexity are problems that we can't really express or manipulate, either. We focus a lot on our ability to create and express solutions because problems in the real world tend to force themselves upon us since long since before computer science was even a thing, but our ability to express problems is limited too!

Moreover, most hard problems are simply proven hard because they incorporate a hard problem.

Eg. Many proofs that say "this problem is NP-Hard" just prove that "you would have to solve xyz NP-Hard problem to solve this"

I'm not clear what you mean -- how else would you prove a problem NP-hard in general? That's usually the most sensible way.

NP-Hardness proofs don't say "you would have to solve xyz NP-Hard problem to solve this", they say "if you could solve the problem you're interested in, you could use the solution to solve all other NP-complete problems". It's not that they incorporate a hard problem -- rather, you show that your problem is hard enough that it can be used to solve other hard problems.

> There are some such algorithms. You don't encounter them as often because we are biased towards encountering algorithms that can be implemented efficiently

Oh, but inverse Ackerman is very slow, and exp(a^(-1)(n)) is very slow as well. Same with the iterated logarithm.

The later pops up in recursive algorithms that partition in parts of size log n. I don't think that's a very weird thing to do.

Those fucntions all map quite well to programming or problem space constructs. For example, Polynomial time comes naturaly from nested loops over the input. Exponential and factorial complexities come naturally from exhaustive searches over combinatorial explosion, and exponentials also crop up in the context of naive recursion. Logs come from anything that looks like "recursively eliminate a fraction of the possibilities".

There is also a discussion of this "level system" of complexities on Lipton and Regan's blog https://rjlipton.wordpress.com/2017/01/04/babais-result-stil...

Reply on news.ycombinator.com