Dlaczego ta funkcja jest obliczalna w czasie ?

My podręcznik mówi „określamy funkcji następująco: i . Zauważ, że biorąc pod uwagę , możemy łatwo znaleźć w czasie liczbę taką, że jest umieszczone pomiędzy i . "$f\colon \mathbb{N}\to\mathbb{N}$$f(1)=2$$f(i+1)=2^{f(i)^{1.2}}$$n$$O(n^{1.5})$$i$$n$$f(i)$$f(i+1)$

Jak mogę się przekonać, że tak naprawdę możemy łatwo znaleźć w czasie ? Ponieważ jest zdefiniowane rekurencyjnie, myślę, że musimy obliczyć aż . Aby dowiedzieć się, ile czasu zajmują te obliczenia, myślę, że musimy znaleźć odpowiednią górną granicę dla zależną od i musimy znaleźć górną granicę na czas wykonania funkcji . Na koniec mamy nadzieję, że pokażemy cytowaną propozycję. Niestety nie widzę ani jednej, ani drugiej.$i$$O(n^{1.5})$$f$$f(1),f(2),f(3)\dots f(j)$$f(j)\geq n$$i$$n$$x\to2^{x^{1.2}}$

Zapomniałem wspomnieć: Należy pamiętać, że jesteśmy w kontekście niedeterministycznym. Stwierdzono więc, że $f$ można obliczać w $O(n^{1.5})$ przez niedeterministyczną maszynę Turinga.

Ponieważ sporo osób już przeczytało to pytanie, a niektóre z nich uważają je za przydatne i interesujące, ale jak dotąd nikt nie odpowiedział, chcę podać więcej informacji na temat kontekstu: cytowane twierdzenie jest integralną częścią dowodu twierdzenie o niedeterministycznej hierarchii czasu. Dowód (wraz z roszczeniem) można znaleźć np. W książce Arory i Baraka , ale znalazłem też sporo innych zasobów w sieci, które przedstawiają ten sam dowód. Każde z nich nazywa roszczenie łatwym lub trywialnym i nie wyjaśnia, jak znaleźć w czasie . Więc albo wszystkie te zasoby, które właśnie skopiowałem z Arory i Baraka, albo roszczenie nie jest wcale takie trudne.$i$$O(n^{1.5})$

Oznacz jakodługość liczby , tj. (dla ). Obliczenie wymaga czasu w modelu RAM, a zatem obliczenie z zajmuje czas . Ponieważ rośnie szybciej niż geometrycznie, całkowity czas na obliczenie wynosi . Jak zauważyłeś, musisz to robić, aż , co oznacza, że . Dlatego całkowity czas działania wynosi$|x|$$x$$\lfloor \log_2 x \rfloor + 1$$x > 0$$2^x$$O(x)$$f(i+1)$$f(i)$$O(f(i)^{1.2}) = O(|f(i+1)|)$$f(i)$$f(i+1)$$O(|f(i+1)|)$$f(i+1) \geq n$$f(i) < n$$O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$ .

W modelu maszyny Turinga z pojedynczą taśmą obliczenie zajmuje czas , a zatem całkowity czas pracy wynosi . Algorytm obliczania zastępuje przez (tutaj to binarna reprezentacja , a to binarna reprezentacja przy użyciu różnych cyfr ), a następnie wielokrotnie uruchamia transformację , co zajmuje czas .$2^x$$O(x\log x)$$O(n^{1.2} \log n) = O(n^{1.5})$$2^x$$[x]$$1[[x]]$$[x]$$x$$[[x]]$$0',1'$$[[x]] \longrightarrow 0[[x-1]]$$O(|x|) = O(\log x)$