Complejidad computacional de pi

Dejar

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

(donde se considera codificado en binario). Entonces, ¿qué podemos decir sobre la complejidad computacional de ? Está claro que . Y si no me equivoco, los sorprendentes algoritmos de "tipo BBP" para calcular el bit de usando el tiempo cuasilineal y la memoria , sin necesidad de calcular los bits anteriores, producen . $n$ $L$ $L\in\mathsf{EXP}$ $n^{th}$ $\pi$ $(\log n)^{O(1)}$ $L\in\mathsf{PSPACE}$

¿Podemos hacerlo aún mejor y colocar (por ejemplo) en la jerarquía de conteo? En la otra dirección, ¿hay algún resultado de dureza para (incluso uno extremadamente débil, como -hardness)? $L$ $L$ $\mathsf{TC}^0$

Un lenguaje relacionado interesante es

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

(donde nuevamente, está escrito en binario). Tenemos $t$

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

y por lo tanto ; Me interesaría mucho si se supiera algo mejor. $L' \in \mathsf{PSPACE}$

cc.complexity-theory na.numerical-analysis Scott Aaronson
fuente

(1) Porque es el número trascendental más famoso y se sabe mucho al respecto. (2) Porque quería un ejemplo concreto. (Por supuesto, también estaría muy interesado en las preguntas análogas para , , etc., en cualquier medida que las respuestas difieran). (3) Porque, para Chaitin's , ya sé la respuesta : a saber, ¡calcular el dígito binario es indiscutible! (Y estoy adivinando que es posible dar una reducción mostrando que el problema de búsqueda subsecuencia es incomputable, así como para ... que nadie vea cómo?)

π

$\pi$

e

$e$

\sqrt{2}

$\sqrt{2}$

Ω

$\Omega$

n^{t h}

$n^{th}$

Ω

$\Omega$

Scott Aaronson

@ScottAaronson, creo que podemos iterar sobre todas las cadenas de longitud y preguntar si está en el idioma; esto nos da todos los primeros bits de .

x

$x$

t

$t$

⟨ x, t ⟩

$\langle x, t \rangle$

t

$t$

Ω

$\Omega$

usul

Tengo un lenguaje similar al "estilo de teoría de números": :-)

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

Por cierto, he comprobado Weihrauch, al final de la sección 7.2 se afirma que el n-ésimo bit de funciones trigonométricas y sus inversas se puede calcular en tiempo usando el firmado representación de dígitos (permitiendo en Además de y como un dígito) en subconjuntos compactos de su dominio. ( es la complejidad de la multiplicación de enteros binarios.)

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

Respuestas:

Bien, James Lee me ha señalado este artículo de 2011 de Samir Datta y Rameshwar Pratap, que demuestra que mi lenguaje (que codifica los dígitos de ) está en el cuarto nivel de la jerarquía de conteo ( ; gracias a SamiD a continuación por señalar un falta en el documento, ¡que simplemente repetí en mi respuesta! ) El documento también discute explícitamente mi cuestión de límites inferiores sobre la complejidad de calcular los dígitos binarios de números irracionales, aunque solo logra demostrar un límite inferior muy débil para calcular los dígitos binarios de números racionales . Esto es exactamente lo que estaba buscando. $L$ $\pi$ $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$ $\mathsf{PP}$

Actualización (3 de abril): una consecuencia divertida de que los dígitos de sean computables en la jerarquía de conteo es la siguiente. Suponga que es un número normal (cuya expansión binaria converge rápidamente a "efectivamente aleatoria"), y suponga que (con la simulación que involucra solo una pequeña sobrecarga polinómica). Entonces sería factible programar su computadora para encontrar, por ejemplo, la primera aparición de los trabajos completos de Shakespeare en la expansión binaria de . Si eso le parece absurdo, entonces tal vez debería tomarse como evidencia adicional de que . :-) $\pi$ $\pi$ $\mathsf{P} = \mathsf{PP}$ $\pi$ $\mathsf{P} \ne \mathsf{PP}$

Scott Aaronson
fuente

OK, pero dice que tengo que esperar 5 horas antes de hacerlo.

Scott Aaronson

Por cierto, el documento mencionado anteriormente esencialmente reduce el problema a y cita erróneamente el límite como . El límite más conocido es actualmente como se muestra aquí: 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