Kompleksitas komputasi pi

Membiarkan

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

(di mana $n$ dianggap dikodekan dalam biner). Lalu apa yang bisa kita katakan tentang kompleksitas komputasi $L$ ? Jelas bahwa $L\in\mathsf{EXP}$ . Dan jika saya tidak salah, algoritma "BBP-type" yang luar biasa untuk menghitung bit n ^ {th} \ pi menggunakan waktu quasilinear dan (\ log n) ^ {O (1)} memori, tanpa harus menghitung bit sebelumnya, hasilkan L \ dalam \ mathsf {PSPACE} .$n^{th}$$\pi$$(\log n)^{O(1)}$$L\in\mathsf{PSPACE}$

Bisakah kita berbuat lebih baik, dan menempatkan $L$ (katakanlah) dalam hierarki penghitungan? Di arah lain, apakah ada hasil kekerasan apa pun untuk $L$ (bahkan yang sangat lemah, seperti $\mathsf{TC}^0$ -kekerasan)?

Bahasa terkait yang menarik adalah

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

(di mana lagi, $t$ ditulis dalam biner). Kita punya

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

dan karenanya $L' \in \mathsf{PSPACE}$ ; Saya akan sangat tertarik jika sesuatu yang lebih baik diketahui.

Oke, James Lee telah mengarahkan saya ke makalah 2011 oleh Samir Datta dan Rameshwar Pratap, yang membuktikan bahwa bahasa saya (penyandian digit ) berada di tingkat keempat hierarki penghitungan ( ; terima kasih kepada SamiD di bawah ini karena menunjukkan hilang di koran, yang saya ulangi saja dalam jawaban saya! ). Makalah ini juga secara eksplisit membahas pertanyaan saya tentang batas bawah pada kompleksitas menghitung angka biner dari angka irasional, meskipun hanya berhasil membuktikan batas bawah yang sangat lemah untuk menghitung angka biner angka rasional . Ini persis apa yang saya cari.$L$$\pi$$\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$$\mathsf{PP}$

Pembaruan (3 April): Konsekuensi lucu dari digit yang dapat dihitung dalam hierarki penghitungan adalah sebagai berikut. Misalkan adalah angka normal (yang ekspansi binernya menyatu dengan cepat menjadi "efektif acak"), dan anggap itu (dengan simulasi yang hanya melibatkan overhead polinomial kecil). Maka akan layak untuk memprogram komputer Anda untuk menemukan, misalnya, kemunculan pertama karya lengkap Shakespeare dalam ekspansi biner dari . Jika itu terdengar tidak masuk akal bagi Anda, maka mungkin itu harus diambil sebagai bukti tambahan bahwa . :-)$\pi$$\pi$$\mathsf{P} = \mathsf{PP}$$\pi$$\mathsf{P} \ne \mathsf{PP}$