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

24

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

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

vtt
la source
billet voté avec bkg / analyse / papiers / liens, mathoverflow, philosophie derrière le travail de mochizuki "
vzn
1
les ressources de polymathe sur l'attaque de Mochizuki , généralement fréquemment mises à jour. liens vers les articles de Mochizukis, discussions récentes, couverture médiatique (MSM), etc.
vzn

Réponses:

25

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

Cela a vraisemblablement un rapport avec le problème contre A C C 0 [ 6 ] .TC0UNECC0[6]

Ryan Williams
la source
22

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

vzn
la source