Exponenciales dobles vs exponenciales simples

Aquí hay cuatro principios que no puedo conciliar:

• Los algoritmos de tiempo exponencial doble se ejecutan en$O(2^{2^{n^k}})$ tiempo con $k \in \mathbb{N}$ constante
• Los algoritmos de tiempo exponencial se ejecutan en$O(2^{n^k})$ con $k \in \mathbb{N}$ constante
• El primer límite crece estrictamente más rápido que el segundo; es decir, existen algoritmos que se ejecutan en tiempo exponencial doble pero no en tiempo exponencial
• Aplicando $a^{b^c} = a^{bc}$ al doble límite exponencial que tenemos $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$, que se encuentra dentro del límite exponencial establecido anteriormente

Siento que me falta algo de sutileza relacionada con la definición de un algoritmo de tiempo exponencial que se ejecuta en $O(2^{\mathrm{poly}(n)})$ más bien que $O(2^{n})$, pero no estoy seguro exactamente dónde radica la sutileza.

El problema se reduce a una terminología ambigua.

$(a^b)^c = a^{bc}$, pero $a^{(b^c)} \neq a^{bc}$. En otras palabras, los exponentes no son asociativos.

Convencionalmente, los exponenciales anidados sin paréntesis se agrupan de esta segunda manera, porque es más útil. Entonces$2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. Si quisiéramos hablar sobre$(2^2)^n$, podríamos escribir $2^{2n}$ en cambio, reservamos la notación exponencial doble para el otro caso.

$a^{(b^c)}$ no es lo mismo que $(a^b)^c$. Cuando la gente escribe$2^{2^k}$, generalmente significan $2^{(2^k)}$no $(2^2)^k$.