Entscheidbarkeit der Gleichheit radikaler Ausdrücke

8

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?Q+,×,,/nn

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

Mees de Vries
quelle
Was sind deine Gedanken? Was hast du versucht und wo bist du festgefahren?
Raphael
@Raphael, um klar zu sein, das sind keine Hausaufgaben oder Nachforschungen - es ist nur eine Frage eines müßigen Geistes. Ich habe noch keine nicht trivialen Gedanken dazu. Offensichtlich ist dies ohne die Wurzeln trivial. Ich bin mir ziemlich sicher, dass die Menge der Polynome in den ten Wurzeln von ganzen Zahlen eine entscheidende Gleichheit aufweist, da die Überprüfung der linearen Unabhängigkeit solcher Wurzeln einfach sein sollte (?). Aber ich stecke völlig fest, wenn es um verschachtelte Radikale oder sogar Bruchteile solcher "radikalen Polynome" geht. n Q.QnQ
Mees de Vries
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Raphael

Antworten:

3

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 xx2x0xx2=x0x

Gemeinschaft
quelle
Schön, aber warum setzen Sie Newline vor den Punkt? Ich habe versucht, Ihren Whitespace-Code zu kompilieren, aber kein Glück.
Evil
Danke für die Antwort! Wir erwarten, dass Referenzen die minimalen wissenschaftlichen Anforderungen erfüllen und im Laufe der Zeit so robust wie möglich sind. Bitte nehmen Sie sich etwas Zeit, um Ihren Beitrag in dieser Hinsicht zu verbessern. Wir haben hier einige Ratschläge gesammelt . Vielen Dank!
DW
3
  1. Algebraische Zahlen sind Lösungen von Polynomen mit rationalen Koeffizienten.
  2. +,×,,/ 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 ] + , × , - , /nnn[1,x,(x2+1)/2]+,×,,/
  5. Zwei Begriffe sind gleich, wenn ihre eindeutigen Darstellungen identisch sind.
Punkt Punkt Punkt
quelle
Ich denke, der wichtige / interessante Teil hier ist der Denesting-Algorithmus. Der Rest funktioniert (auch ohne den Denesting-Algorithmus, da verschachtelte Radikale eindeutig algebraisch sind, auch wenn Sie nicht wissen, wie man sie denestiert), ist aber eine Art Kanone für eine Fliege.
Mees de Vries
Danke für die Antwort! Wir erwarten, dass Referenzen die minimalen wissenschaftlichen Anforderungen erfüllen und im Laufe der Zeit so robust wie möglich sind. Bitte nehmen Sie sich etwas Zeit, um Ihren Beitrag in dieser Hinsicht zu verbessern. Wir haben hier einige Ratschläge gesammelt . Vielen Dank!
DW