Decydująca teoria asymptotycznego wzrostu

12

Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x2 x lg ( x + 2 ) ?” lub „Czy 2 lg xO ( lg lg x ) ?”.NNxx2xlg(x+2)2lgxO(lglgx)

Jeśli ograniczymy funkcje do wielomianów (wyrażonych w zwykły sposób), nie będzie to trudne. Zobacz także normalną formę Cantor .

Jak duże możemy uczynić klasę funkcji, zanim porównanie stanie się nierozstrzygalne? Czy możemy rozszerzyć go na funkcje używane w typowej klasie algorytmów licencjackich?

Jak wyjaśnia Joshua Grochow w komentarzach, naprawdę interesuje mnie zestaw wyrażeń, a nie same funkcje. Tak więc, na przykład, byłbym zainteresowany procedurami decyzyjnymi, które mogłyby porównywać „ ” i „ 2 ”, nawet jeśli nie mogą porównać „ ln e ” i „ n ( ln n ) - 1 ”.12lnen(lnn)1

Ewentualnie powiązane pytanie: „Czy teoria granic asymptotycznych jest całkowicie aksjomatyczna?”

jbapple
źródło
2
Interesujące pytanie! Myślę, że jedną część należy nieco zmienić. Nie sądzę, aby pytanie dotyczyło tego, jak duża jest klasa funkcji, ale raczej, w jaki sposób funkcje są wyrażane . Oznacza to, że jeśli jako dane wejściowe podano dwie maszyny Turinga o wielomianowym czasie, stwierdzenie, który z nich ma większy czas działania, jest nierozstrzygalne (pomimo faktu, że oba mają wielomianowe czasy działania) ... Jeśli te funkcje byłyby zamiast tego wyrażone jako, powiedzmy , wyraźne wielomiany (wypisz cały współczynnik poli w / współczynniki), a następnie łatwo je porównać.
Joshua Grochow
Słuszna uwaga. Czy masz jakieś sugestie, jak to sformułować?
jbapple
1
Myślę, że to zależy od tego, co cię interesuje. Naturalne może być zapytanie o funkcje wyrażone jako formuła obejmująca różne operacje, a wtedy pytanie brzmi, jakie zestawy operacji sprawiają, że jest to rozstrzygalne / nierozstrzygalne. np. ops będzie zawierał +, czasy, dzielenie, -, n-te korzenie, exp, log, kompozycja, log ^ * itd. (Jeśli pominąć log ^ *, poprzednia lista daje wszystkie podstawowe funkcje.)
Joshua Grochow

Odpowiedzi:

9

Rxexplog||f(x)5+f(x)=xjest w rodzinie). Hardy wykazał, że dowolne dwie takie funkcje można porównać asymptotycznie. Nie jestem pewien, czy dowód jest algorytmiczny, ale warto to sprawdzić.

Boshernitzan rozszerzył tę klasę jeszcze bardziej i bez wątpienia istnieją inne prace na ten temat.

Yuval Filmus
źródło
Książka Johna R. Shackella „Symboliczne asymptotyki” (sekcja 5.1, strona 91) twierdzi, że pierwszy algorytm tego problemu pochodzi z pracy Dahna i Goringa z 1986 r. „Uwagi na temat terminów wykładniczo-logarytmicznych” . Rozprawa Dominika Gruntza z 1996 r. „O limitach obliczeniowych w symbolicznym systemie manipulacji” również zawiera algorytm tego problemu i porównuje różne metody.
jbapple
2
Jednak wszystkie one opierają się na wyroczni w celu rozwiązania problemu zerowej równoważności, co ogólnie jest nierozstrzygalne.
jbapple