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

Improve this question
$\endgroup$
3
  • 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, 2014 at 4:10
  • $\begingroup$ Good point. Do you have any suggestions about how to word that? $\endgroup$
    – jbapple
    Jan 26, 2014 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, 2014 at 4:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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