Complexité informatique de pi

31

Laisser

L={n:the nth binary digit of π is 1}

(où n est considéré comme codé en binaire). Que dire alors de la complexité de calcul de ? Il est clair que . Et si je ne me trompe pas, les incroyables algorithmes de "type BBP" pour calculer le bit de utilisant le temps quasi-linéaire et la mémoire , sans avoir besoin de calculer les bits précédents, donnent .L E XLLEXPnthπ(logn)O(1)LPSPACE

Pouvons-nous faire encore mieux et placer (disons) dans la hiérarchie de comptage? Dans l'autre sens, y a-t-il un résultat de dureté quelconque pour (même extrêmement faible, comme -dureté)?LLTC0

Une langue apparentée intéressante est

L={x,t:x occurs as a substring within the first t digits of π}

(où encore, est écrit en binaire). On at

LNPL

et donc ; Je serais extrêmement intéressé si quelque chose de mieux était connu.LPSPACE

Scott Aaronson
la source
9
(1) Parce que est le nombre transcendantal le plus célèbre, et on en sait beaucoup sur lui. (2) Parce que je voulais un exemple concret. (Je serais bien sûr également très intéressé par les questions analogues pour e , πe , etc., dans quelle mesure les réponses diffèrent.) (3) Parce que, pour leΩde Chaitin, je connais déjà la réponse: à savoir, calculer len t h chiffre binaire n'est pas calculable! (Et jesupposequ'il est possible de donner une réduction montrant que le problème de recherche de sous-séquence est également non calculable pourΩ... tout le monde voit comment?)2ΩnthΩ
Scott Aaronson
6
@ScottAaronson, je pense que nous pouvons itérer sur toutes les chaînes de longueur t et demander si x , t est dans la langue; cela nous donne tous les t premiers bits de Ω . xtx,ttΩ
usul
3
J'ai un langage "de type théorie des nombres" similaire: :-)L={n the second lower bit of the n-th prime number is 1}
Marzio De Biasi
3
Soit dit en passant, j'ai vérifié Weihrauch, à la fin de la section 7.2, il indique que le n-ième bit des fonctions trigonométriques et leurs inverses peuvent être calculés dans le temps utilisant la représentation à chiffres signés (permettant - 1 dans en plus de 0 et 1 en tant que chiffre) sur des sous-ensembles compacts de leur domaine. ( t m est la complexité de la multiplication d'entiers binaires.)tm(n)lgn101tm
Kaveh

Réponses:

26

OK, James Lee m'a pointé sur cet article de 2011 de Samir Datta et Rameshwar Pratap, qui prouve que ma langue (codant les chiffres de π ) est au quatrième niveau de la hiérarchie de comptage ( P H P P P P P P ; merci à SamiD ci-dessous pour avoir signalé un P P manquant dans le journal, que j'avais simplement répété dans ma réponse!). L'article traite également explicitement de ma question des bornes inférieures sur la complexité du calcul des chiffres binaires des nombres irrationnels, bien qu'il ne parvienne qu'à prouver une borne inférieure très faible pour le calcul des chiffres binaires du rationnel.LπPHPPPPPPPPNombres. Ceci est exactement ce que je cherchais.

Mise à jour (3 avril): Une conséquence amusante du fait que les chiffres de sont calculables dans la hiérarchie de comptage est la suivante. Supposons que π est un nombre normal (dont l'expansion binaire converge rapidement vers "effectivement aléatoire"), et supposons que P = P P (avec la simulation impliquant seulement une petite surcharge polynomiale). Il serait alors possible de programmer votre ordinateur pour trouver, par exemple, la première occurrence des travaux complets de Shakespeare dans l'expansion binaire de π . Si vous semble absurde, alors peut - être il devrait être considéré comme une preuve supplémentaire que PP P . :-)ππP=PPπPPP

Scott Aaronson
la source
D'accord, mais ça dit que je dois attendre 5 heures avant de le faire!
Scott Aaronson
7
BTW, le document mentionné ci - dessus permet de réduire sensiblement le problème de et cite de façon erronée la tenue en P H P P P P . La limite la plus connue est actuellement P H P P P P P P comme indiqué ici: eccc.hpi-web.de/report/2013/177BitSLPPHPPPPPHPPPPPP
SamiD