Complexidade computacional do pi

31

Deixei

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

(onde é considerado codificado em binário). Então, o que podemos dizer sobre a complexidade computacional de L ? É claro que L E X P . E, se não me engano, os incríveis algoritmos "do tipo BBP" para calcular o n t h bit de π usando tempo quase linear e ( log n ) O ( 1 ) de memória, sem precisar calcular os bits anteriores, produzem L P S P A C E .nLLEXPnthπ(logn)O(1)LPSPACE

Podemos melhorar ainda mais e colocar (por exemplo) na hierarquia de contagem? Na outra direção, existe algum resultado de dureza para L (mesmo um extremamente fraco, como a dureza T C 0 )?LLTC0

Uma linguagem relacionada interessante é

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

(onde, novamente, é escrito em binário). Nós temost

LNPL

e, portanto, ; Eu ficaria extremamente interessado se algo melhor fosse conhecido.LPSPACE

Scott Aaronson
fonte
9
(1) Porque é o número transcendental mais famoso e muito se sabe sobre ele. (2) Porque eu queria um exemplo concreto. (Obviamente, eu também estaria muito interessado nas questões análogas para e , πe , etc., em qualquer medida as respostas diferem) (3) Porque, para de Chaitin.Ω, eu já sei a resposta: ou seja, calcular on t h dígito binário é uncomputable! (E eu estousupondoque é possível dar uma redução mostrando que o problema de pesquisa subsequence é uncomputable, bem como paraΩ... ninguém vê como?)2ΩnthΩ
Scott Aaronson
6
@ScottAaronson, acho que pode iterar sobre todas as cordas de comprimento t e perguntar se x , t é na língua; isso nos dá todos os primeiros t bits de Ω .xtx,ttΩ
usul 28/03
3
Eu tenho um similar "-teoria-style número" língua: :-)L={n the second lower bit of the n-th prime number is 1}
Marzio De Biasi
3
By the way, I checked Weihrauch, at the end of section 7.2 it states that n-th bit of trigonometric functions and their inverses can be computed in time tm(n)lgn using the signed-digit representation (allowing 1 in addition to 0 and 1 as a digit) on compact subsets of their domain. (tm is the complexity of binary integer multiplication.)
Kaveh

Respostas:

26

OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language L (encoding the digits of π) is in the fourth level of the counting hierarchy (PHPPPPPP; thanks to SamiD below for pointing out a missing PP in the paper, which I'd simply repeated in my answer!). The paper also explicitly discusses my question of lower bounds on the complexity of computing the binary digits of irrational numbers, though it only manages to prove a very weak lower bound for computing the binary digits of rational numbers. This is exactly what I was looking for.

Update (April 3): An amusing consequence of the digits of π being computable in the counting hierarchy is as follows. Suppose that π is a normal number (whose binary expansion converges quickly to "effectively random"), and suppose that P=PP (with the simulation involving only a small polynomial overhead). Then it would be feasible to program your computer to find, for example, the first occurrence of the complete works of Shakespeare in the binary expansion of π. If that sounds absurd to you, then maybe it should be taken as additional evidence that PPP. :-)

Scott Aaronson
fonte
OK, but it says I have to wait 5 hours before doing so!
Scott Aaronson
7
BTW, The paper mentioned above essentially reduces the problem to BitSLP and erroneously quotes the bound as PHPPPP. The best known bound is currently PHPPPPPP as shown here: eccc.hpi-web.de/report/2013/177
SamiD