Entscheidende Theorie des asymptotischen Wachstums

Was sind die bekannten Grenzen der Entscheidbarkeit des Vergleichs der Wachstumsrate von Funktionen von ? Ich denke hier an die Entscheidbarkeit von Fragen wie "Ist ?" oder "Ist ?". $\mathbb{N} \to \mathbb{N}$ $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$ $2^{\lg^* x} \in O(\lg \lg x)$

Wenn wir die Funktionen auf Polynome beschränken (in der üblichen Weise ausgedrückt), ist dies nicht schwer. Siehe auch Cantor-Normalform .

Wie groß kann die Klasse der Funktionen sein, bevor der Vergleich unentscheidbar wird? Können wir es auf die Funktionen erweitern, die in einer typischen Algorithmusklasse für Studenten verwendet werden?

Wie Joshua Grochow in den Kommentaren erklärt, interessiert mich wirklich die Menge der Ausdrücke, nicht die Funktionen selbst. Ich würde mich zum Beispiel für Entscheidungsverfahren interessieren, die " " und " " vergleichen können, auch wenn sie " " und " " nicht vergleichen können . $1$ $2$ $\ln e$ $n^{(\ln n)^{-1}}$

Möglicherweise verwandte Frage: "Ist die Theorie der asymptotischen Grenzen endlich axiomatisierbar?"

decidability asymptotics Apfel
quelle

Interessante Frage! Ich denke, ein Teil sollte allerdings ein bisschen geändert werden. Ich denke nicht, dass die Frage sein sollte, wie groß die Klasse von Funktionen ist, sondern wie die Funktionen ausgedrückt werden . Das heißt, wenn Sie zwei Turing-Maschinen mit Polynomzeit als Eingabe erhalten, ist es nicht zu entscheiden, welche Maschine eine längere Laufzeit hat (trotz der Tatsache, dass beide Polynomlaufzeiten haben) ... Wenn diese Funktionen stattdessen wie folgt ausgedrückt würden: , explizite Polynome (schreiben Sie die gesamten Poly w / Koeffizienten aus), dann ist es einfach zu vergleichen.

Joshua Grochow

Guter Punkt. Haben Sie Vorschläge, wie Sie das ausdrücken können?

Jbapple

Ich denke, es hängt davon ab, woran Sie interessiert sind. Es kann natürlich sein, nach Funktionen zu fragen, die als Formel mit verschiedenen Operationen ausgedrückt werden. Dann stellt sich die Frage, durch welche Operationsgruppen sie entscheidbar / unentscheidbar werden. Beispiel: ops würde +, times, divide, -, n-te Wurzel, exp, log, composition, log ^ * usw. enthalten. (Wenn Sie log ^ * weglassen, enthält die vorhergehende Liste alle elementaren Funktionen.)

Joshua Grochow

Antworten:

Hardy betrachtete in seinem klassischen Buch Orders of Infinity die Klasse der logarithmisch-exponentiellen Funktionen. Dies ist eine eher allgemeine Klasse von Funktionen, bei der es sich um die minimale Menge von Funktionen handelt, die und , die unter Addition, Multiplikation und Division (sofern sie nicht unendlich viele Nullen enthält) geschlossen werden und unter und (gleiche Bedingung) und geschlossen unter Lösung von Polynomgleichungen (dh die Funktion, die erfüllt $\mathbb{R}$ $x$ $\exp$ $\log|\cdot|$ $f(x)^5 + f(x) = x$ ist in der Familie). Hardy zeigte, dass zwei solche Funktionen asymptotisch verglichen werden können. Ich bin nicht sicher, ob der Beweis algorithmisch ist, aber es lohnt sich zu überprüfen.

Boshernitzan hat diese Klasse noch erweitert, und es gibt zweifellos andere Arbeiten zu diesem Thema.

Yuval Filmus
quelle

John R. Shackells Buch "Symbolic Asymptotics" (Abschnitt 5.1, Seite 91) behauptet, der erste Algorithmus für dieses Problem stamme aus Dahns und Görings Arbeit von 1986 "Notes on exponential-logarithmic terms" . Dominik Gruntz '1996 erschienene Dissertation "Über die Berechnung von Grenzen in einem symbolischen Manipulationssystem" enthält ebenfalls einen Algorithmus für dieses Problem und vergleicht verschiedene Methoden.

Jbapple

Diese stützen sich jedoch alle auf ein Orakel zur Lösung des im Allgemeinen unentscheidbaren Nulläquivalenzproblems.

Jbapple