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

8

Considérez les termes construits à partir d'éléments de Q et les opérations +,×,,/, et n 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).

Mees de Vries
la source
Quelles sont vos pensées? Qu'avez-vous essayé et où êtes-vous resté coincé?
Raphael
@Raphael, pour être clair, ce ne sont pas des devoirs ou de la recherche - c'est juste une question d'esprit oisif. Je n'ai pas encore de pensées non triviales à ce sujet. Évidemment, c'est trivial sans les racines. Je suis sûr que l'ensemble desQ-polynômes en ne racines d'entiers a une égalité décidable, car la vérification Q-l'indépendance linéaire de telles racines devrait être facile (?). Mais je suis complètement bloqué en ce qui concerne les radicaux imbriqués, ou même des fractions de ces "polynômes radicaux".
Mees de Vries
Continuons cette discussion dans le chat .
Raphael

Réponses:

3

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 nombresx, x2 et x sont à la fois bien formés et x2=x Si et seulement si 0x, 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 .

Communauté
la source
Bien, mais pourquoi mettez-vous la nouvelle ligne avant le point? J'ai essayé de compiler votre code d'espaces blancs, mais pas de chance.
Evil
Merci d'avoir répondu! Nous nous attendons à ce que les références remplissent les exigences universitaires minimales et soient aussi robustes que possible dans le temps. Veuillez prendre le temps d'améliorer votre message à cet égard. Nous avons rassemblé quelques conseils ici . Je vous remercie!
DW
3
  1. Les nombres algébriques sont des solutions de polynômes à coefficients rationnels.
  2. +,×,,/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,(x2+1)/2]). Cette représentation permet une évaluation symbolique de+,×,,/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.
point point point
la source
J'ai l'impression que la partie importante / intéressante ici est l'algorithme de dénégation; le reste fonctionne (même sans l'algorithme de dénégation, car les radicaux imbriqués sont clairement algébriques même si vous ne savez pas comment les dénier), mais c'est une sorte de canon pour une mouche.
Mees de Vries
Merci d'avoir répondu! Nous nous attendons à ce que les références remplissent les exigences universitaires minimales et soient aussi robustes que possible dans le temps. Veuillez prendre le temps d'améliorer votre message à cet égard. Nous avons rassemblé quelques conseils ici . Je vous remercie!
DW