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}$

cc.complexity-theory na.numerical-analysis

— Scott Aaronson
źródło

(1) Ponieważ jest najbardziej znaną liczbą transcendentalną i wiele o niej wiadomo. (2) Ponieważ chciałem konkretnego przykładu. (Byłbym oczywiście bardzo zainteresowany analogicznymi pytaniami dla , itd., Niezależnie od tego, w jakim stopniu odpowiedzi będą się różnić). (3) Ponieważ dla Chaitina już znam odpowiedź : mianowicie obliczenie cyfry binarnej jest niemożliwe do obliczenia ! (I przypuszczam, że można zmniejszyć, pokazując, że problem wyszukiwania podsekwencji jest również nie do obliczenia dla ... ktoś widzi jak?)

π

$\pi$

e

$e$

\sqrt{2}

$\sqrt{2}$

Ω

$\Omega$

n^{t h}

$n^{th}$

Ω

$\Omega$

— Scott Aaronson

@ ScottAaronson, myślę, że możemy iterować po wszystkich ciągach długości zapytać, czy jest w języku; daje nam to wszystkie pierwsze bity .

x

$x$

t

$t$

⟨ x, t ⟩

$\langle x, t \rangle$

t

$t$

Ω

$\Omega$

— usul

Mam podobny język w stylu teorii liczb: :-)

L = {n ∣ the second lower bit of the n -th prime number is 1}

$L = \{ n \mid \text{ the second lower bit of the }n\text{-th prime number is } 1\}$

— Marzio De Biasi

Nawiasem mówiąc, sprawdziłem Weihraucha, na końcu sekcji 7.2 stwierdza, że n-ty kawałek funkcji trygonometrycznych i ich odwrotności można obliczyć w czasie przy użyciu podpisanej reprezentacji cyfr (pozwalając w oprócz i jako cyfra) w zwartych podzbiorach ich domeny. ( to złożoność binarnego mnożenia liczb całkowitych.)

t_{m} (n) \lg n

$t_m(n) \lg n$

- 1

$-1$

0

$0$

1

$1$

t_{m}

$t_m$

— Kaveh

cs.nyu.edu/exact/doc/pi-log.pdf

— sdcvvc

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}$

— Scott Aaronson
źródło

OK, ale mówi, że muszę to poczekać 5 godzin!

— Scott Aaronson

BTW, Wspomniany powyżej artykuł zasadniczo redukuje problem do i błędnie cytuje granicę jako . Najbardziej znaną granicą jest obecnie jak pokazano tutaj: eccc.hpi-web.de/report/2013/177

B i t S L P

$\mathsf{BitSLP}$

P H^{P P^{P P}}

$\mathsf{PH^{PP^{PP}}}$

P H^{P P^{P P^{P P}}}

$\mathsf{PH^{PP^{PP^{PP}}}}$

— SamiD