Décidabilité de l'égalité des expressions radicales

Considérez les termes construits à partir d'éléments de $\mathbb Q$ et les opérations $+,\times,-,/$, et $\sqrt[n]{\,\cdot\,}$ pour chaque nombre naturel $n$. Étant donné la promesse que deux termes sont bien formés - c'est-à-dire qu'il n'y a pas de division par zéro et même pas de racines de nombres négatifs - existe-t-il un algorithme qui décide quand les deux termes sont égaux?

Une question connexe a été publiée ici , mais elle est plus générale (car elle permet une exponentiation arbitraire, plutôt que simplement par des nombres rationnels).

Oui. Par l'analogue en nombre réel de la transformation de Tseytin , qui se
réduit à la théorie existentielle des réels , qui est dans PSPACE par

page 291 et le bas de la page 290 de ce document
et
les réponses à cette question

.


Pour tous les vrais nombres$x$, $\sqrt{x^2}$ et $x$ sont à la fois bien formés et $\sqrt{x^2} = x$ Si et seulement si $0\leq x$, Donc tester l' inégalité se réduit à votre problème. Je ne connais pas de meilleure limite supérieure pour tester les inégalités de sommes de racines carrées que cet article , qui le place dans la hiérarchie de comptage .

1. Les nombres algébriques sont des solutions de polynômes à coefficients rationnels.
2. $+,\times,-,/$des nombres algébriques donnent des nombres algébriques parce que les nombres algébriques forment un champ ( 1 ). Cela signifie que les radicaux imbriqués sont également des nombres algébriques ( 2 ).
3. Les radicaux imbriqués peuvent être dénigrés par algorithme ( 3 , 4 ).
4. Chaque nombre algébrique de degré $n$ peut être uniquement représenté comme $n$ par $n$ matrice d'entiers sous une base appropriée (par exemple, $[1,x, (x^2+1)/2]$). Cette représentation permet une évaluation symbolique de$+,\times,-,/$par addition de matrice, multiplication et inverse (p.159 de 5 , 6 , 7 ).
5. Deux termes sont égaux si leurs représentations uniques sont identiques.