Treten Funktionen mit langsamerem Wachstum als inverse Ackermann-Funktionen im Laufzeitbereich auf?

Einige komplizierte Algorithmen ( Union-Find ) haben die nahezu konstante inverse Ackermann-Funktion, die in der asymptotischen Zeitkomplexität auftritt, und sind im ungünstigsten Fall zeitoptimal, wenn der nahezu konstante inverse Ackermann-Term ignoriert wird.

Gibt es Beispiele für bekannte Algorithmen mit Laufzeiten, bei denen Funktionen wesentlich langsamer wachsen als inverse Ackermann-Funktionen (z. B. Inverse von Funktionen, die bei polynomiellen oder exponentiellen Transformationen usw. nicht mit Ackermann äquivalent sind), die die bekannteste Worst-Case-Zeit ergeben? Komplexität zur Lösung des zugrunde liegenden Problems?

Seth Pettie hat einen Algorithmus zur Berechnung der Empfindlichkeit eines minimalen Spannbaums in der Zeit , der einen Algorithmus von Tarjan verbessert, der dieselbe in der Zeit O ( m α ( m , n) berechnet ) ) . (Vergleichen Sie dies mit Chazelles O ( m α ( m , n ) ) - Algorithmus zur Berechnung des minimalen Spannbaums$O(m\log \alpha(m,n))$$O(m\alpha(m,n))$$O(m\alpha(m,n))$ selbst.) Das Empfindlichkeitsproblem verlangt, für ein gegebenes Diagramm und einen gegebenen minimalen Spannbaum zu berechnen, um wie viel sich jedes Kantengewicht ändern kann, ohne den minimalen Spannbaum zu ändern.

(Vielen Dank an Tsvi Kopelowitz für diesen Hinweis.)

Die komischste langsam wachsende Funktion, die ich jemals ernsthaft in einem Papier gesehen habe, ist $\alpha^*(n)$, die Häufigkeit, mit der Sie den Ackermann invers anwenden müssen, um ihn fallen zu lassen $n$zu einer festen Konstante. Es wird in diesem Artikel über die Deque-Vermutung auf Spreizbäumen verwendet .

When Alan Turing discovered the computer, there used to be several models for the computer proposed. Turing proved that some (3) of these models could simulate each other AND compute the Ackermann function, whereas the other models could simulate each other but not the Ackermann function (so they could not simulate the 3). Therefore, these 3 models (Turing Machine, von Neumann and one I don't know), were chosen as the architecture for a computer. This does not mean the Ackermann function is the limit of the computer, but I suppose it's hard science. I'm not aware of any computable functions that grow faster than the Ackermann function.

Nun, ich glaube nicht, dass es ein praktisches Problem gibt, das zu Ihrer Frage passt, aber vielleicht können wir eines konstruieren. Wir müssen die Eingabe jedoch einschränken. Da wir O (n) nicht verwenden können, können wir nicht die gesamte Eingabe überprüfen. Tatsächlich können wir nicht einmal die Länge der Eingabe überprüfen, da dies O (log n) wäre. Als ersten Parameter benötigen wir also eine Darstellung der Länge des restlichen Eingangs, zum Beispiel c, so dass Ackermann (c) die Länge des Eingangs ist. Da dies auch nicht geeignet ist, fordern wir als ersten Wert in unserer Eingabe den Parameter c an, so dass bb (c) ungefähr die Länge der Eingabe ist, wobei bb die Besetztbiberfunktion ist. Diese Funktion ist nicht ausführbar, aber bb (c) existiert auf jeden Fall. Dann lautet der Algorithmus wie folgt:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

Mit dem Algorithmus soll überprüft werden, ob c die Inverse von bb ist und ob die Eingabelänge größer als bb (c) ist.

Wenn es eine berechenbare Funktion gibt, die schneller wächst als die Ackermann-Funktion, können wir sie meines Erachtens verwenden, um einen Algorithmus zu erstellen, der Ihre Frage bei jeder Eingabe beantwortet.