Decidabilidad de la igualdad de expresiones radicales

Considere los términos construidos a partir de elementos de y las operaciones y para cada número natural . Dada la promesa de que dos términos están bien formados, es decir, no hay división por cero y ni siquiera raíces de números negativos, ¿existe un algoritmo que decida cuándo los dos términos son iguales?$\mathbb Q$$+,\times,-,/$$\sqrt[n]{\,\cdot\,}$$n$

Aquí se publicó una pregunta relacionada , pero es más general (ya que permite la exponenciación arbitraria, en lugar de solo por números racionales).

Si. Por el análogo de números reales de la transformación de Tseytin , eso se
reduce a la teoría existencial de los reales , que está en PSPACE por

página 291 y la parte inferior de la página 290 de este documento
y
las respuestas a esta pregunta

.


Para todos los números reales , y son tanto bien formada y si y sólo si , por lo que las pruebas La desigualdad se reduce a su problema. No conozco ningún límite superior mejor para probar las desigualdades de sumas de raíces cuadradas que este artículo , que lo ubica en la jerarquía de conteo .$x$$\sqrt{x^2}$$x$$\sqrt{x^2} = x$$0\leq x$

1. Los números algebraicos son soluciones de polinomios con coeficientes racionales.
2. $+,\times,-,/$ de números algebraicos resultan en números algebraicos porque los números algebraicos forman un campo ( 1 ). Esto significa que los radicales anidados también son números algebraicos ( 2 ).
3. Los radicales anidados pueden ser denestados por algoritmo ( 3 , 4 ).
4. Cada número algebraico de grado puede representarse de manera única como una matriz de enteros por bajo una base adecuada (por ejemplo, ). Esta representación permite la evaluación simbólica de por adición de matriz, multiplicación e inversa (p.159 de 5 , 6 , 7 ).$n$$n$$n$$[1,x, (x^2+1)/2]$$+,\times,-,/$
5. Dos términos son iguales si sus representaciones únicas son idénticas.