Złożoność obliczeniowa pi

Pozwolić

$L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$

(gdzie jest uważane za zakodowane w systemie binarnym). Co zatem możemy powiedzieć o złożoności obliczeniowej ? Oczywiste jest, że . I jeśli się nie mylę, niesamowite algorytmy typu „BBP” do obliczania bitu przy użyciu quasilinear czasu i , bez konieczności obliczania poprzednie bity dają .$n$$L$$L\in\mathsf{EXP}$$n^{th}$$\pi$$(\log n)^{O(1)}$$L\in\mathsf{PSPACE}$

Czy możemy zrobić jeszcze lepiej i umieścić (powiedzmy) w hierarchii liczenia? Z drugiej strony, czy jest jakikolwiek wynik twardości dla (nawet bardzo słabego, jak twardość)?$L$$L$$\mathsf{TC}^0$

Interesującym powiązanym językiem jest

$L' = \{ \langle x,t\rangle : x\text{ occurs as a substring within the first }t\text{ digits of }\pi \}$

(gdzie znowu jest zapisywane binarnie). Mamy$t$

$L' \in \mathsf{NP}^L$

i stąd ; Byłbym bardzo zainteresowany, gdyby wiadomo było coś lepszego.$L' \in \mathsf{PSPACE}$

OK, James Lee wskazał mi ten artykuł Samira Datty i Rameshwar Pratap z 2011 roku, który dowodzi, że mój język (kodowanie cyfr ) znajduje się na czwartym poziomie hierarchii liczenia ( ; dzięki SamiD poniżej za wskazanie brakującego w gazecie, który po prostu powtórzyłem w mojej odpowiedzi! ). Artykuł wyraźnie omawia moje pytanie o dolne granice złożoności obliczania cyfr binarnych liczb nieracjonalnych, chociaż udowadnia jedynie bardzo słabą dolną granicę obliczania cyfr binarnych liczb wymiernych . Właśnie tego szukałem.$L$$\pi$$\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$$\mathsf{PP}$

Aktualizacja (3 kwietnia): Zabawna konsekwencja obliczania cyfr w hierarchii liczenia jest następująca. Załóżmy, że jest liczbą normalną (której interpretacja binarna szybko zbiega się w „efektywnie losową”), i załóżmy, że (przy symulacji obejmującej jedynie niewielki narzut wielomianowy). Wtedy byłoby możliwe zaprogramowanie komputera, aby znalazł, na przykład, pierwsze wystąpienie kompletnych dzieł Szekspira w binarnym rozszerzeniu . Jeśli brzmi to dla ciebie absurdalnie, być może należy to uznać za dodatkowy dowód, że . :-)$\pi$$\pi$$\mathsf{P} = \mathsf{PP}$$\pi$$\mathsf{P} \ne \mathsf{PP}$