Eksponensial ganda vs eksponensial tunggal

Inilah empat prinsip yang tidak bisa saya rekonsiliasi:

• Algoritma waktu eksponensial ganda dijalankan di$O(2^{2^{n^k}})$ waktu dengan $k \in \mathbb{N}$ konstan
• Algoritma waktu eksponensial berjalan di$O(2^{n^k})$ dengan $k \in \mathbb{N}$ konstan
• Ikatan yang pertama tumbuh lebih cepat daripada yang terakhir; yaitu, ada algoritma yang berjalan dalam waktu eksponensial ganda tetapi tidak dalam waktu eksponensial
• Menerapkan $a^{b^c} = a^{bc}$ untuk ikatan eksponensial ganda yang kita miliki $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$, yang termasuk dalam batas eksponensial yang dinyatakan sebelumnya

Saya merasa saya kehilangan beberapa kehalusan yang berkaitan dengan definisi algoritma eksponensial waktu berjalan di $O(2^{\mathrm{poly}(n)})$ daripada $O(2^{n})$, tapi saya tidak yakin persis di mana letak kehalusannya.

Masalahnya bermuara pada terminologi yang ambigu.

$(a^b)^c = a^{bc}$tapi $a^{(b^c)} \neq a^{bc}$. Dengan kata lain, eksponen tidak asosiatif.

Secara konvensional, eksponensial bersarang tanpa tanda kurung dikelompokkan dalam cara kedua ini, karena lebih berguna. Begitu$2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. Jika kita ingin membicarakannya$(2^2)^n$, kita bisa menulis $2^{2n}$ sebagai gantinya, jadi kami menyimpan notasi eksponensial ganda untuk kasus lainnya.

$a^{(b^c)}$ tidak sama dengan $(a^b)^c$. Ketika orang menulis$2^{2^k}$Mereka biasanya berarti $2^{(2^k)}$tidak $(2^2)^k$.