Fungsi yang berguna antara polylogaritmik dan polinomial?

8

Saya bertanya-tanya apakah ada fungsi yang berguna asimtotik lebih besar dari fungsi polylogaritmik dan kurang dari fungsi polinom.

Artinya, fungsi sedemikian rupaf(n)

f(n)=ω(log(n)k) untuk beberapa konstantak>0

dan

f(n)=Hai(nk) untuk beberapa konstantak>0

Yang saya maksud dengan berguna, adalah bahwa itu digunakan dalam pembuktian, algoritme, dll. Bukan hanya menghasilkan fungsi yang sesuai dengan batasan ini.

ryan
sumber

Jawaban:

7

Menurut Wikipedia (yang mengaitkan hasil berikut ini dengan Knuth), waktu berjalan dari algoritma Toom – Cook tingkat campuran untuk perkalian integer adalah Fungsi adalah super-polylogarithmic tetapi sub-polinomial.

Θ(ncatatann22catatann).
22catatann
Yuval Filmus
sumber