Que implicações uma prova da conjectura abc teria para os tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
Que implicações uma prova da conjectura abc teria para os tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
Respostas:
Bhatnagar, Gopalan, e Lipton mostram que, assumindo que a conjectura ABC, existem polinómios de grau representando o limiar-de- k função sobre Z 6 . Para a constante fixa k , e m, que possui t fatores primos, a conjectura abc implica um polinômio para Limiar de k sobre Z m com grau O ( n 1 / t + ε ) .O((kn)1/2+ε) k Z6 k m t k Zm O(n1/t+ε)
Presumivelmente, isso tem relevância para o problema versus A C C 0 [ 6 ] .TC0 ACC0[6]
fonte
este artigo aponta que o cálculo do valor da raiz quadrada recíproca usando a representação de ponto flutuante é generalizado em aplicativos de CS ("muito comum em cálculos científicos"); os autores mostram que é possível uma fórmula mais eficiente para calcular o valor arredondado corretamente se a conjectura ABC se mantiver.
[1] A conjectura abc e as raízes quadradas recíprocas corretamente arredondadas Ernie Croot, Ren-Cang Li, Hui June Zhu, Elsevier TCS 2004
[2] cálculo rápido da raiz quadrada inversa, wikipedia
fonte