Teori pertumbuhan asimptotik yang dapat dipertimbangkan

Apa batas yang diketahui dari kesesuaian perbandingan tingkat pertumbuhan fungsi dari ? Saya di sini memikirkan kepantasan pertanyaan seperti "Apakah x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?" atau "Apakah 2 lg ∗ x ∈ O ( lg lg x ) ?".$\mathbb{N} \to \mathbb{N}$$x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$$2^{\lg^* x} \in O(\lg \lg x)$

Jika kita membatasi fungsi menjadi polinomial (diekspresikan dengan cara biasa), maka ini tidak sulit. Lihat juga bentuk normal penyanyi .

Seberapa besar kita dapat membuat kelas fungsi sebelum perbandingan menjadi tidak dapat ditentukan? Bisakah kita memperluasnya ke fungsi yang digunakan dalam kelas algoritma sarjana khas?

Seperti yang dijelaskan Joshua Grochow di komentar, saya benar-benar tertarik pada rangkaian ekspresi, bukan fungsi itu sendiri. Jadi, misalnya, saya akan tertarik dengan prosedur keputusan yang dapat membandingkan " " dan " 2 ", bahkan jika mereka tidak dapat membandingkan " ln e " dan " n ( ln n ) - 1 ".$1$$2$$\ln e$$n^{(\ln n)^{-1}}$

Pertanyaan yang mungkin terkait: "Apakah teori batas asimptotik tidak dapat diterima?"

$\mathbb{R}$$x$$\exp$$\log|\cdot|$$f(x)^5 + f(x) = x$ada di keluarga). Hardy menunjukkan bahwa dua fungsi tersebut dapat dibandingkan tanpa gejala. Saya tidak yakin apakah buktinya algoritmik, tetapi perlu diperiksa.

Boshernitzan memperpanjang kelas ini lebih jauh, dan tidak diragukan lagi ada pekerjaan lain tentang masalah ini.