Decidibilidade da igualdade de expressões radicais

Considere os termos criados a partir dos elementos de e as operações +, \ times, -, / , e \ sqrt [n] {\, \ cdot \,} para cada número natural n . Dada a promessa de que dois termos são bem-formados - isto é, não há divisão por zero e nem raízes de números negativos - existe um algoritmo que decide quando os dois termos são iguais?$\mathbb Q$$+,\times,-,/$$\sqrt[n]{\,\cdot\,}$$n$

Uma questão relacionada foi postada aqui , mas é mais geral (pois permite exponenciação arbitrária, e não apenas por números racionais).

Sim. Pelo análogo em número real da transformação de Tseytin , isso se
reduz à teoria existencial dos reais , que está no PSPACE por

página 291 e parte inferior da página 290 deste artigo
e
as respostas a esta pergunta

.


Para todos os números reais , e são ambos bem formado e se e somente se , então o teste a desigualdade se reduz ao seu problema. Não conheço nenhum limite superior melhor para testar desigualdades de somas de raízes quadradas do que este artigo , que o coloca na hierarquia de contagem .$x$$\sqrt{x^2}$$x$$\sqrt{x^2} = x$$0\leq x$

1. Os números algébricos são soluções de polinômios com coeficientes racionais.
2. $+,\times,-,/$ de números algébricos resultam em números algébricos porque os números algébricos formam um campo ( 1 ). Isso significa que os radicais aninhados também são números algébricos ( 2 ).
3. Radicais aninhados podem ser despojados pelo algoritmo ( 3 , 4 ).
4. Cada número algébrica de grau pode ser representado de forma única como um por matriz de inteiros sob uma base adequada (por exemplo, ). Essa representação permite a avaliação simbólica de por adição de matriz, multiplicação e inversa (p.159 de 5 , 6 , 7 ).$n$$n$$n$$[1,x, (x^2+1)/2]$$+,\times,-,/$
5. Dois termos são iguais se suas representações únicas forem idênticas.