36
$\begingroup$

Let

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

(where $n$ is thought of as encoded in binary). Then what can we say about the computational complexity of $L$? It's clear that $L\in\mathsf{EXP}$. And if I'm not mistaken, the amazing "BBP-type" algorithms for computing the $n^{th}$ bit of $\pi$ using quasilinear time and $(\log n)^{O(1)}$ memory, without needing to compute the previous bits, yield $L\in\mathsf{PSPACE}$.

Can we do even better, and place $L$ (say) in the counting hierarchy? In the other direction, is there any hardness result whatsoever for $L$ (even an extremely weak one, like $\mathsf{TC}^0$-hardness)?

An interesting related language is

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

(where again, $t$ is written in binary). We have

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

and hence $L' \in \mathsf{PSPACE}$; I'd be extremely interested if anything better is known.

Improve this question
$\endgroup$
14
  • 11
    $\begingroup$ (1) Because $\pi$ is the most famous transcendental number, and a lot is known about it. (2) Because I wanted a concrete example. (I would, of course, also be very interested in the analogous questions for $e$, $\sqrt{2}$, etc., to whatever extent the answers differ.) (3) Because, for Chaitin's $\Omega$, I already know the answer: namely, computing the $n^{th}$ binary digit is uncomputable! (And I'm guessing it's possible to give a reduction showing that the subsequence search problem is uncomputable as well for $\Omega$ ... anyone see how?) $\endgroup$
    – Scott Aaronson
    Mar 28, 2014 at 17:24
  • 6
    $\begingroup$ @ScottAaronson, I think we can iterate over all strings $x$ of length $t$ and ask if $\langle x, t \rangle$ is in the language; this gives us all of the first $t$ bits of $\Omega$. $\endgroup$
    – usul
    Mar 28, 2014 at 18:11
  • 4
    $\begingroup$ I have a similar "number-theory-style" language: $L = \{ n \mid \text{ the second lower bit of the }n\text{-th prime number is } 1\}$ :-) $\endgroup$
    – Marzio De Biasi
    Mar 28, 2014 at 19:01
  • 3
    $\begingroup$ 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 $t_m(n) \lg n$ using the signed-digit representation (allowing $-1$ in addition to $0$ and $1$ as a digit) on compact subsets of their domain. ($t_m$ is the complexity of binary integer multiplication.) $\endgroup$
    – Kaveh
    Mar 29, 2014 at 5:25
  • 8
    $\begingroup$ cs.nyu.edu/exact/doc/pi-log.pdf $\endgroup$
    – sdcvvc
    Mar 29, 2014 at 19:44

1 Answer 1

Reset to default
30
$\begingroup$

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 $\pi$) is in the fourth level of the counting hierarchy ($\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$; thanks to SamiD below for pointing out a missing $\mathsf{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 $\pi$ being computable in the counting hierarchy is as follows. Suppose that $\pi$ is a normal number (whose binary expansion converges quickly to "effectively random"), and suppose that $\mathsf{P} = \mathsf{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 $\pi$. If that sounds absurd to you, then maybe it should be taken as additional evidence that $\mathsf{P} \ne \mathsf{PP}$. :-)

Improve this answer
$\endgroup$
2
  • $\begingroup$ OK, but it says I have to wait 5 hours before doing so! $\endgroup$
    – Scott Aaronson
    Mar 30, 2014 at 10:18
  • 7
    $\begingroup$ BTW, The paper mentioned above essentially reduces the problem to $\mathsf{BitSLP}$ and erroneously quotes the bound as $\mathsf{PH^{PP^{PP}}}$. The best known bound is currently $\mathsf{PH^{PP^{PP^{PP}}}}$ as shown here: eccc.hpi-web.de/report/2013/177 $\endgroup$
    – SamiD
    Mar 31, 2014 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.