Llame a la anterior identidad $R$, y donde $X$ $Y$ son dos expresiones en $\wedge$, dicen que $X =_R Y$ fib $X$ $Y$ puede ser probada equivalente, utilizando $R$.
Intuitivamente, una expresión exponencial $X$ es equivalente a $x^{\prod T_i}$ para algunos variable $x$ y expresiones exponenciales $T_i$. Pero no podemos usar los productos de aquí, así que define inductivamente la secuencia de $T_X$ de las ramas de $X$ : $T_v = ()$, $T_{A^B} = (B).T_A$, donde el punto indica la concatenación. También definir a la izquierda de la variable $\ell(X)$ $\ell(v) = v$, $\ell(A^B) = \ell(A)$.
Lema. Expresiones exponenciales se $R$-equivalente iff su izquierda variables son iguales y sus secuencias de las ramas se $R$-equivalente (hasta permutación).
La prueba de esto es bastante largo, pero sencillo.
Parece obvio que si tenemos dos diferentes expresiones exponenciales en $x$ y algunas constantes, uno debe ser poco-o de la otra. Sin embargo, como vamos a ver, tenemos una relación que juega bien con la multiplicación, de manera similar al big-O de obras con la adición. En particular, necesitamos algo como $f, g \le h \implies f \cdot g \le h$, similar a la de la suma propiedad para big-O.
El pensamiento acerca de hyper operadores, parece la cosa más natural que hacer es subir big-O un nivel en la jerarquía:
Para las funciones de $f, g : \mathbb{N} \to \mathbb{N}$, dicen que $f \le_\wedge g$ fib no es $n \ge 1$ tal que $f \le_{ev} g^n$ donde $ \le_{ev}$ significa que "con el tiempo, a menos que o igual a", y $g^n(x) := g(x)^n$.
Sin embargo, ya que estamos tratando de separar las funciones (y $f = g \implies f \le_\wedge g$), haremos uso de la negación de esta relación: $f >_\wedge g$ fib no es cierto que $f \le_\wedge g$.
Teorema. Si $X$ $Y$ son expresiones en $\wedge$ y una sola variable $x$ que no son $R$-equivalente, a continuación, $X <_\wedge Y$ o $Y <_\wedge X$ (considerado como funciones de $\mathbb{N} \to \mathbb{N}$).
(El contrapositivo parece limpiador para demostrar mirando hacia atrás, pero esto requiere de la inversión de la totalidad de la prueba.)
Debería ser posible demostrar algo similar para el caso general, mediante la fijación de todas las variables, excepto $x$, pero hay complicaciones.
Prueba. Desde $\ell(X) = \ell(Y)$, $T_X$ y $T_Y$ no $R$-equivalente como multisets. Si hay algo en $T_X$ $R$- equivalente a algo en $T_Y$, eliminar a los dos y seguir haciendo esto hasta que no hay ningún tipo de parejas. Llame a la resultante de las secuencias de $T_X'$$T_Y'$. Ahora, vamos a proceder por la fuerte inducción en la expresión de la altura/tamaño. $T_X'$ $T_Y'$ no puede estar vacío, porque, a continuación,$X =_R Y$. Así que consideren $S = T_X' \cup T_Y'$ (considerados como conjuntos). Desde $S$ no $R$-duplicados, por hipótesis, es linealmente ordenado por $<_\wedge$. Vamos $M = \max S$. $M$ (se considera como una función) está en cualquiera de las $T_X'$ o $T_Y'$, pero no tanto. WLOG es en $T_X'$.
Lema. $<_\wedge$ es una irreflexiva relación que satisface (1) $d <_\wedge f \le_{ev} p \implies d <_\wedge p$ y (2) $f \le_{ev} g <_\wedge h \implies fg <_\wedge h$.
Prueba. $\le_\wedge$ es claramente reflexivo.
(1) Si $p \le_\wedge d$, luego de algunos $n$ tenemos $p \le_{ev} d^n$, lo $f \le_{ev} d^n$.
(2) Si $h \le_\wedge fg$, luego de algunos $n$, $h \le_{ev} (fg)^n \le_{ev} g^{2n}$.
Corolario. $<_\wedge$ es transitiva, y por otra parte $f <_\wedge g$ implica $f^2 <_\wedge g$.
Ahora observe que la primera de todas, $M \le_{ev} \prod T_X'$. Y para cualquier $T, U \in T_Y'$ tenemos $T \le_{ev} U <_\wedge M$. Por lo tanto, por el lema anterior, si escribimos las ramas en $T_Y'$ en un orden basado en la $\le_{ev}$ (que coincide con $<_\wedge$ , excepto cuando dos términos son iguales) y, sucesivamente, "unir" dos ramas adyacentes multiplicando, tendremos $\prod T_Y' <_\wedge M$. Por lo tanto $\prod T_Y' <_\wedge \prod T_X'$.
Lema. Si hay algo de $N$ tal que $1 < N \le_{ev} g$$f \in O(g) \implies f \le_\wedge g$.
Prueba. $f \le_{ev} Mg$ algunos $M$ (WLOG $M \ge 1$) por $f \le_{ev} N^{\log_N(M)} g \le_{ev} g^{\log_N(M) + 1}$. Y desde $M \ge 1$ y $N > 1$, $\log_N(M) > 0$.
Esta condición sostiene claramente para todas las funciones que estamos considerando. Por lo tanto, $\prod T_X' \notin O(\prod T_Y')$, así que para todos los $M$, no es cierto que $x^{\prod T_Y'} \le_{ev} x^{M\prod T_X'} = (x^{\prod T_X'})^M$, y si tenemos que agregar de nuevo en los duplicados, la misma no se sostiene con $T_X$ $T_Y$ (desde $f^h \le_{ev} g^h$ implica $f \le_{ev} g$ $f, g, h$ que son, finalmente, no es igual a 1 o 0). QED.
