Computabilidade de igualdade a zero para uma linguagem simples

7

Suponha que tenhamos uma árvore na qual as folhas sejam rotuladas com um conjunto de números Le nós internos com um conjunto de operações O.

Em particular L pode ser N,Z ou Qe, opcionalmente, pode conter π e / ou e. O pode ser qualquer subconjunto de {+,,,/, ^}.

A igualdade com zero é decidível? As comparações de sinais são decidíveis? Se sim, eles são viáveis?

Operações "inválidas" (0/0, 00, ...) produzir NaN, NaN0 e NaN propaga através de cálculos, como de costume.

Algumas combinações são triviais: se nos restringirmos às operações de campo e não incluirmos π ou e no Lentão podemos calcular a fração resultante e terminar com ela. Ou se restringirmos aZ{π} e {+,,}podemos calcular o polinômio e verificar os coeficientes. Por outro lado, poderes (e, portanto,n-ésimas raízes) e π e e tornar as coisas consideravelmente mais difíceis.

O problema "igualdade com zero" é uma instância do problema constante .

miniBill
fonte

Respostas:

4

Se você usar os operadores {+,,×,/} (ou seja, você não incluiu o operador de energia), todos os seus problemas provavelmente são decidíveis.

Testando igualdade com zero

Por exemplo, vamos considerar L=Z{π}. Então você pode tratarπ como um símbolo formal, de modo que cada folha seja um polinômio em Z[π] (por exemplo, o número inteiro 5 é o polinômio constante 5; π é o polinômio π+0do grau 1). Agora você pode expressar a árvore como um polinômio racional sobreZcom π como o desconhecido formal.

Suponha que esse polinômio seja p(π)/q(π). Teste sep(π) é o polinômio zero (grau ) Se não for o polinômio zero, a expressão não será igual a zero. E sep(π) é o polinômio zero e q(π)não é o polinômio zero, então a expressão é igual a zero. A correção deste procedimento decorre do fato de queπé transcendental .

Qual é a complexidade deste procedimento? A resposta depende do modelo computacional. Vamos supor que cada operador gaste um tempo constante para avaliar (independentemente do tamanho dos operandos). Então a complexidade depende do tamanho dos polinômios resultantes. O grau do polinômio pode crescer exponencialmente com a profundidade da árvore. Portanto, se você construir o polinômio recursivamente e expressá-lo explicitamente (em forma de coeficiente), o tempo de execução será no máximo exponencial na profundidade da árvore. Felizmente, o grau cresce no máximo linearmente no número de folhas na árvore; portanto, o tempo de execução de um algoritmo determinístico é linear no tamanho da árvore.

Portanto, assumindo uma representação direta da árvore e um modelo computacional simplista, isso fornece um algoritmo de tempo linear para teste zero quando os operadores estão {+,,×,/}.

Este procedimento não funciona apenas para L=Z{π}, mas também para N{π} e Q{π}.

O mesmo procedimento também funciona para L=Q{π,e}, se pudermos assumir uma conjectura razoável: que π e esão algebricamente independentes. Não se sabe se essa conjectura está correta, mas parece provável. Enfim, aqui está a abordagem. Tratamos o polinômio como um polinômio multivariado em duas incógnitasπ,eem vez de um desconhecido, mas tudo continua como antes, dada a independência algébrica deπ e e. Também funciona paraL=Z{π,e} e L=N{π,e}também, novamente, assumindo a conjectura.

Se você quiser ser extravagante, poderá usar algoritmos aleatórios para teste de identidade polinomial. E seL=Z{π}, eles terão o seguinte: escolha um primo aleatório r e um número inteiro aleatório sπ{0,,r1}; substitua cada instância deπ com sπ; e verifique se a expressão resultante é avaliada como0modr. (Se você possui e , escolhe dois inteiros aleatórios e .) Você pode repetir esse teste várias vezes. Se esse procedimento fornecer algo diferente de zero (módulo ), a expressão original certamente será diferente de zero. Se sempre der zero (módulo ), com alta probabilidade, a expressão original será igual a zero. Isso pode ser mais eficiente em alguns modelos computacionais (por exemplo, onde o tempo para avaliar um único operador depende do tamanho dos operandos).πesπserr

Comparação de sinal

Você também pode encontrar o sinal da expressão usando procedimentos semelhantes (novamente, assumindo que você excluiu o operador ^ e novamente, assumindo que e são algebricamente independentes). Avalie a expressão como um polinômio racional sobre . Suponha que você tenha determinado que e . Você quer saber se ou não.πep(π,e)/q(π,e)Q[π,e]p(π,e)/q(π,e)0q(π,e)0p(π,e)/q(π,e)>0

Aqui está uma abordagem. Observe que se . Portanto, podemos formar um novo polinômio e reduzi-lo ao problema de avaliar o sinal de . Basicamente, precisamos avaliar o sinal de um polinômio racional em e . Sabemos que isso é avaliado como algo diferente de zero.p(π,e)/q(π,e)>0p(π,e)q(π,e)>0r(π,e)=p(π,e)q(π,e)r(π,e)πe

Uma abordagem é a de calcular e para bits de precisão, e em seguida avaliar em conformidade, ganhando limites inferiores e superiores de . Se 0 for incluído nesse intervalo, duplo , até que o limite inferior seja estritamente positivo ou o limite inferior seja estritamente negativo.πekr(π,e)r(π,e)k

Qual é a complexidade dessa abordagem? Sefor avaliado como um valor , acho que o tempo de execução será polinomial no tamanho da entrada e em .|r(π,e)|ϵlg1/ϵ

Pode haver um algoritmo melhor, mas este é o melhor que posso apresentar agora.

Conclusão

O argumento é que o operador de energia (^) é a verdadeira fonte de dificuldade. Sem o operador de energia, todos os seus problemas podem ser resolvidos sem muita dificuldade (assumindo uma conjectura razoável).

DW
fonte
11
Não se sabe que e são algebricamente independentes. πe
Yuval Filmus
O algoritmo de sinal parece interessante, obrigado! Enfim, como disse Yuval, não sabemos sobre a independência
miniBill
4

Esta é uma pergunta bastante complicada! Como você parece entender, o problema real é a presença de . Está intimamente relacionado a uma conjectura bem conhecida: a conjectura de Schanuel , que afirma que, essencialmente, não existem relações algébricas não triviais entre e .^πe

A resposta positiva (esperada) a esta conjectura daria a você um procedimento de decisão para comparação com :0

  • Reduza a expressão usando igualdades algébricas (por exemplo etc.)(xy)z=xyz
  • Separe os termos com expoentes e os termos sem.
  • Verifique se a base ( em ) dos termos com expoentes é linearmente independente.xxy
  • O termo é 0 se for trivial, ou seja, reduz a 0 por operações algébricas.

Uma questão relacionada é o problema da função exponencial de Tarski, que envolve variáveis. No entanto, é relativamente simples reduzir expressões concretas com expoentes a funções com variáveis, dado o teorema de Lindemann-Wierstrass .

Edit: Eu não sei nada sobre a complexidade real do problema, no entanto. Observe que isso depende muito do seu modelo computacional, por exemplo, se as operações aritméticas são constantes.

Edit 2: Cometi um erro crucial: não é a base em que precisa ser tomada, mas sim , que é muito mais difícil de verificar a independência linear.xxyyln(x)

cody
fonte
Meu modelo computacional é um computador real (com memória infinita é claro)
miniBill
Como sobre coisas como Como você reduzi-la?(((pie)pi)+pie(1/2)
miniBill
11
Suponho que você esteja perguntando sobre a expressão . Nesse caso, já está "reduzido". Tudo o que você precisa verificar é que , e são linearmente independentes e deduz que a expressão é diferente de zero, pois seus exponenciais devem ser algebricamente independentes . (πe)π+πe1/2(πe)ln(π)ln(π)1/2
Cody #
Como você verifica algoritticamente a independência linear?
miniBill
Hummm. Não tenho certeza, na verdade. É bastante fácil mostrar que é transcendental assumindo a conjectura, mas estou perplexo com . Vou editar minha resposta. eππln(πe)
Cody