Implications de la preuve de la conjecture abc pour la théorie cs

Quelles implications une preuve de la conjecture abc aurait-elle pour tcs?

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

Bhatnagar, Gopalan et Lipton montrent que, en supposant que la conjecture abc, il existe des polynômes de degré représentant le seuil-of- k fonction sur Z 6 . Pour la constante fixe k et m qui a t facteurs premiers, la conjecture abc implique un polynôme pour le seuil de k sur Z m de degré O ( n 1 / t + ε ) .$O((kn)^{1/2+\varepsilon})$$k$${\mathbb Z}_6$$k$$m$$t$$k$$\mathbb Z_m$$O(n^{1/t+\varepsilon})$

Cela a vraisemblablement un rapport avec le problème contre A C C 0 [ 6 ] .${\sf TC^0}$$\sf ACC^0[6]$

cet article souligne que le calcul de la valeur de la racine carrée réciproque en utilisant la représentation en virgule flottante est répandu dans les applications CS ("très courant dans les calculs scientifiques"); les auteurs montrent qu'une formule plus efficace est possible pour calculer la valeur correctement arrondie si la conjecture ABC tient.

[1] La conjecture abc et les racines carrées réciproques correctement arrondies Ernie Croot, Ren-Cang Li, Hui June Zhu, Elsevier TCS 2004

[2] calcul rapide de la racine carrée inverse, wikipedia