Théorie décidable de la croissance asymptotique

Quelles sont les limites connues de la décidabilité de la comparaison du taux de croissance des fonctions de ? Je pense ici à la décidabilité de questions comme "Est-ce que ?" ou "Est-ce que ?". $\mathbb{N} \to \mathbb{N}$ $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$ $2^{\lg^* x} \in O(\lg \lg x)$

Si nous limitons les fonctions à des polynômes (exprimés de la manière habituelle), alors ce n'est pas difficile. Voir aussi forme normale de Cantor .

Quelle peut être la taille de la classe de fonctions avant que la comparaison ne devienne indécidable? Pouvons-nous l'étendre aux fonctions utilisées dans une classe d'algorithmes de premier cycle typique?

Comme l'explique Joshua Grochow dans les commentaires, je m'intéresse vraiment à l'ensemble des expressions, pas aux fonctions elles-mêmes. Ainsi, par exemple, je serais intéressé par des procédures de décision qui pourraient comparer " " et " ", même s'ils ne peuvent pas comparer " " et " ". $1$ $2$ $\ln e$ $n^{(\ln n)^{-1}}$

Question éventuellement liée: "La théorie des bornes asymptotiques est-elle finement axiomatisable?"

decidability asymptotics jbapple
la source

Question interessante! Je pense qu'une partie devrait être un peu modifiée cependant. Je ne pense pas que la question devrait être la taille de la classe de fonctions, mais plutôt la façon dont les fonctions sont exprimées . Autrement dit, si vous disposez de deux machines de Turing à temps polynomial en entrée, dire lequel a un temps de fonctionnement plus long est indécidable (malgré le fait que les deux ont des temps de fonctionnement polynomiaux) ... Si ces fonctions étaient plutôt exprimées comme, disons , des polynômes explicites (écrivez le poly entier avec les coefficients), alors c'est facile à comparer.

Joshua Grochow

Bon point. Avez-vous des suggestions sur la façon de formuler cela?

jbapple

Je suppose que cela dépend de ce qui vous intéresse. Il pourrait être naturel de demander des fonctions exprimées sous forme de formule impliquant diverses opérations, puis la question est de savoir quels ensembles d'opérations la rendent décidable / indécidable. Par exemple, les opérations incluraient +, les temps, la division, -, les racines nième, exp, log, composition, log ^ *, etc. (Si vous omettez log ^ *, la liste précédente vous donne toutes les fonctions élémentaires.)

Joshua Grochow

Hardy, dans son livre classique Orders of infinity , a considéré la classe des fonctions logarithmiques-exponentielles. Il s'agit d'une classe de fonctions plutôt générale, qui est l'ensemble minimal de fonctions contenant et , fermées sous addition, multiplication et division (sauf si elle contient une infinité de zéros), fermées sous et(même contrainte), et fermé sous solution d'équations polynomiales (ie la fonction satisfaisant est dans la famille). Hardy a montré que deux de ces fonctions peuvent être comparées asymptotiquement. Je ne sais pas si la preuve est algorithmique, mais cela vaut la peine d'être vérifié. $\mathbb{R}$ $x$ $\exp$ $\log|\cdot|$ $f(x)^5 + f(x) = x$

Boshernitzan a étendu cette classe encore plus loin, et il y a sans doute d'autres travaux sur le sujet.

Yuval Filmus
la source

Le livre de John R. Shackell, «Symbolic Asymptotics», affirme (section 5.1, page 91), que le premier algorithme pour ce problème provenait de l'article de Dahn et Goring de 1986, «Notes on exponential-logarithmic terms» . La dissertation de Dominik Gruntz de 1996, "Sur les limites de calcul dans un système de manipulation symbolique" contient également un algorithme pour ce problème et compare diverses méthodes.

jbapple

Cependant, tous s'appuient sur un oracle pour résoudre le problème d'équivalence zéro, qui est indécidable en général.

jbapple

Théorie décidable de la croissance asymptotique

Réponses: