12
$\begingroup$

What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$?" or "Is $2^{\lg^* x} \in O(\lg \lg x)$?".

If we restrict the functions to be polynomials (expressed in the usual manner), then this isn't hard. See also Cantor normal form.

How large can we make the class of functions before comparison becomes undecidable? Can we extend it to the functions used in a typical undergraduate algorithms class?

As Joshua Grochow explains in the comments, I'm interested really in the set of expressions, not the functions themselves. So, for instance, I'd be interested in decision procedures that could compare "$1$" and "$2$", even if they can't compare "$\ln e$" and "$n^{(\ln n)^{-1}}$".

Possibly related question: "Is the theory of asymptotic bounds finitely axiomatizable?"

$\endgroup$
  • 2
    $\begingroup$ Interesting question! I think one part should be changed a bit though. I don't think the question should be how large the class of functions is, but rather how the functions are expressed. That is, if you're given two polynomial-time Turing machines as input, telling which one has a larger running time is undecidable (despite the fact that both have polynomial running times)... If those functions were instead expressed as, say, explicit polynomials (write out the whole poly w/ coefficients) then it's easy to compare. $\endgroup$ – Joshua Grochow Jan 26 '14 at 4:10
  • $\begingroup$ Good point. Do you have any suggestions about how to word that? $\endgroup$ – jbapple Jan 26 '14 at 4:24
  • 1
    $\begingroup$ I guess it depends what you're interested in. It might be natural to ask for functions expressed as formula involving various operations, and then the question is what sets of operations make it decidable/undecidable. e.g. ops would include +, times, divide, -, nth roots, exp, log, composition, log^*, etc. (If you leave out log^*, the preceding list gives you all elementary functions.) $\endgroup$ – Joshua Grochow Jan 26 '14 at 4:53
9
$\begingroup$

Hardy, in his classical book Orders of infinity, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same constraint), and closed under solution of polynomial equations (i.e. the function satisfying $f(x)^5 + f(x) = x$ is in the family). Hardy showed that any two such functions can be compared asymptotically. I'm not sure if the proof is algorithmic, but it is worth checking.

Boshernitzan extended this class even further, and doubtlessly there is other work on the subject.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.