Czy funkcje o wolniejszym wzroście niż odwrotny Ackermann pojawiają się w granicach środowiska wykonawczego?

Niektóre skomplikowane algorytmy ( szukanie związku ) mają prawie stałą odwrotną funkcję Ackermanna, która pojawia się w asymptotycznej złożoności czasowej, i są optymalne w najgorszym przypadku, jeśli prawie stały odwrotny termin Ackermanna jest ignorowany.

Czy istnieją przykłady znanych algorytmów z czasami działania, które obejmują funkcje, które rosną zasadniczo wolniej niż odwrotny Ackermann (np. Odwrotności funkcji, które nie są równoważne Ackermannowi w transformacjach wielomianowych lub wykładniczych itp.), Które dają najbardziej znany czas najgorszego przypadku złożoność rozwiązania podstawowego problemu?

reference-request algorithm-analysis time-complexity runtime-analysis użytkownik2566092
źródło

Algorytmy czasowe

? Pytasz o znany problem, którego najlepiej znanym algorytmem jest

? Najpierw musisz znaleźć funkcję rosnącą „zasadniczo szybciej” niż

, taką jak DRZEWO

, a następnie wziąć jej odwrotność, a następnie znaleźć problem, który do niej pasuje!

O (1)

$O(1)$

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

Pål GD

istnieją dowolne, wymyślone algorytmy zbudowane z hierarchii czasu thm

vzn

@vzn: Dowolne

nie jest konstruowalne w czasie (co obejmuje

). Zatem nie można tutaj zastosować twierdzenia o hierarchii czasu.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

mdxn

@mdx cieszę się, że ktoś to zauważył, po prostu testuję, że mrugasz tak, ostatnio myślałem, że może istnieć uogólnienie hierarchii czasu thm dla funkcji pod-

. ale w każdym razie limit

wynika z tego, że konstruowalna w czasie TM musi odczytać wszystkie dane wejściowe, ale czy mówimy te inne algorytmy, np. z odwrotną złożonością czasową Ackermanna, prawda? problemy z wizualizacją tego! czuję, że pytanie dotyczy bardziej istnienia pod-

języków .... czy może gdzieś jest jakaś ankieta lub opis ....

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

wer 5'13

@vzn: OP naprawdę musi wyjaśnić, jaki model obliczeń mają na myśli.

należy zdefiniować w bazach TM o swobodnym dostępie (lub ich odpowiednikach). Określając naszą mechanikę, możemy przypadkowo dodać za dużo mocy. Może być nawet w takim stopniu, w którym pojęcie złożoności obliczeniowej nie jest owocne. Mówiąc najprościej, musielibyśmy zmienić nasze pojęcie złożoności czasowej (co robi zamortyzowane środowisko wykonawcze) z ryzykiem, że taka definicja może stać się bardzo wymyślna (to samo dotyczy modelu obliczeniowego).

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

mdxn

Odpowiedzi:

$O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$ sam.) Problem wrażliwości wymaga obliczenia, dla danego wykresu i danego minimalnego drzewa opinającego, o ile każda waga krawędzi może się zmienić bez zmiany minimalnego drzewa opinającego.

(Podziękowania dla Tsvi Kopelowitz za ten odnośnik.)

Yuval Filmus
źródło

Nie wiem, czy odwrotny log Ackermann jest „zasadniczo wolniejszy” niż odwrotny Ackermann, ale taki czas pracy mnie zaskoczył.

Yuval Filmus

$\alpha^*(n)$ $n$

templatetypedef
źródło

-1

Kiedy Alan Turing odkrył komputer, zaproponowano kilka modeli tego komputera. Turing udowodnił, że niektóre (3) z tych modeli mogą się symulować ORAZ obliczać funkcję Ackermanna, podczas gdy inne modele mogą symulować się nawzajem, ale nie funkcję Ackermanna (więc nie mogą symulować 3). Dlatego te 3 modele (Turing Machine, von Neumann i jeden, którego nie znam) zostały wybrane jako architektura komputera. Nie oznacza to, że funkcja Ackermanna jest granicą komputera, ale przypuszczam, że to twarda nauka. Nie znam żadnych obliczalnych funkcji, które rosną szybciej niż funkcja Ackermanna.

Nie sądzę, aby istniał problem praktyczny pasujący do twojego pytania, ale być może uda nam się go rozwiązać. Musimy jednak nałożyć ograniczenia na dane wejściowe. Ponieważ nie możemy użyć O (n), nie możemy sprawdzić całego wejścia. W rzeczywistości nie możemy nawet sprawdzić długości danych wejściowych, ponieważ byłoby to O (log n). Zatem jako pierwszy parametr potrzebujemy reprezentacji długości reszty danych wejściowych, na przykład c, tak aby Ackermann (c) był długością danych wejściowych. Ponieważ nie jest to również odpowiednie, jako pierwszą wartość w naszym danych wejściowych wymagamy parametru c, tak aby bb (c) był mniej więcej długości wejścia, gdzie bb jest funkcją bobra zajętego. Ta funkcja jest niepoprawna, ale bb (c) z pewnością istnieje. Następnie algorytm wygląda następująco:

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

Algorytm ma na celu sprawdzenie, czy jeśli c jest odwrotnością bb, to wtedy długość wejściowa jest większa niż bb (c).

Jeśli istnieje funkcja obliczalna, która rośnie szybciej niż funkcja Ackermanna, myślę, że możemy użyć jej odwrotności do stworzenia algorytmu, który odpowie na twoje pytanie na dowolnym wejściu.

Albert Hendriks
źródło

Zdecydowanie istnieją funkcje, które rosną szybciej niż funkcja Ackermanna, jak wskazano w komentarzach (DRZEWO (n)). Trudna część pytania polega na konstruowaniu algorytmu z ograniczeniem w czasie wykonywania odwrotności tej funkcji. Taka maszyna nie ma wystarczająco dużo czasu na obliczenie odwrotności funkcji, więc konstrukcja TM, która to osiąga, nie jest prosta.

mdxn