5 ms·

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(

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?

jerf 10y ago
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!
- VodkaHaze 10y ago
  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"
  - CJefferson 10y ago
    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.
  - moyix 10y ago
    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.
- thomasahle 10y ago
  > 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.
cousin_it 10y ago
The iterated logarithm, a very slow-growing function, shows up naturally in algorithm analysis: https://en.wikipedia.org/wiki/Iterated_logarithm https://en.wikipedia.org/wiki/Iterated_logarithm. And the inverse Ackermann of course shows up in union-find.
- repsilat 10y ago
  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.
pdpi 10y ago
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".
thomasahle 10y ago
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-still-a-breakthrough/ https://rjlipton.wordpress.com/2017/01/04/babais-result-stil...

jerf 10y ago

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!

VodkaHaze 10y ago
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"
- CJefferson 10y ago
  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.
- moyix 10y ago
  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.
thomasahle 10y ago
> 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.

cousin_it 10y ago

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

repsilat 10y ago
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.

pdpi 10y ago

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

thomasahle 10y ago

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-still-a-breakthrough/ https://rjlipton.wordpress.com/2017/01/04/babais-result-stil...