Entscheidbarkeit der Gleichheit radikaler Ausdrücke

Betrachten Sie Begriffe, die aus Elementen von und den Operationen und für jede natürliche Zahl . Gibt es angesichts des Versprechens, dass zwei Terme gut geformt sind - das heißt, es gibt keine Division durch Null und keine geraden Wurzeln negativer Zahlen - einen Algorithmus, der entscheidet, wann die beiden Terme gleich sind?$\mathbb Q$$+,\times,-,/$$\sqrt[n]{\,\cdot\,}$$n$

Eine verwandte Frage wurde hier gestellt , ist aber allgemeiner (da sie eine willkürliche Potenzierung erlaubt und nicht nur durch rationale Zahlen).

Ja. Durch die Echt Zahl Analogon der Tseitin-Transformation , die
zu reduziert die existentielle Theorie der reellen Zahlen , die in ist PSPACE durch

Seite 291 und das Ende von Seite 290 aus diesem Dokument
und
die Antworten auf diese Frage

.


Für alle reellen Zahlen , und sind beide wohlgeformt und , wenn und nur wenn , Prüfung so Ungleichheit reduziert sich auf Ihr Problem. Mir ist keine bessere Obergrenze für das Testen von Ungleichungen von Quadratwurzelsummen bekannt als dieses Papier , das es in die Zählhierarchie einordnet .$x$ x$\sqrt{x^2}$$x$0≤$\sqrt{x^2} = x$$0\leq x$

1. Algebraische Zahlen sind Lösungen von Polynomen mit rationalen Koeffizienten.
2. $+,\times,-,/$ von algebraischen Zahlen führen zu algebraischen Zahlen, da algebraische Zahlen ein Feld bilden ( 1 ). Dies bedeutet, dass verschachtelte Radikale auch algebraische Zahlen sind ( 2 ).
3. Verschachtelte Radikale können durch den Algorithmus ( 3 , 4 ) denestiert werden .
4. Jede algebraische Zahl vom Grad eindeutig als dargestellt werden durch - Matrix von ganzen Zahlen unter einer geeigneten Basis (beispielsweise ). Diese Darstellung ermöglicht die symbolische Auswertung von durch Matrixaddition, Multiplikation und Inverse (S.159 von 5 , 6 , 7 ).n n [ 1 , x , ( x 2 + 1 ) / 2 ] + , × , - , $n$$n$$n$$[1,x, (x^2+1)/2]$$+,\times,-,/$
5. Zwei Begriffe sind gleich, wenn ihre eindeutigen Darstellungen identisch sind.