Implicações da prova de conjectura ABC para a teoria cs

24

Que implicações uma prova da conjectura abc teria para os tcs?

http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/

vtt
fonte
ver também a prova reivindicada para conexão entre primos por Ball, Natureza
vzn
post com mais votos com bkg / analysis / papers / links, mathoverflow, filosofia por trás do trabalho de
mochizuki
11
recursos polymath no ataque Mochizuki , geralmente atualizados com freqüência. links para documentos de Mochizukis, discussões recentes, cobertura da mídia (MSM) etc
vzn

Respostas:

25

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+ε)kZ6kmtkZmO(n1/t+ε)

Presumivelmente, isso tem relevância para o problema versus A C C 0 [ 6 ] .TC0ACC0[6]

Ryan Williams
fonte
22

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

vzn
fonte