Вычислительная сложность пи

Позволять

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

(где считается закодированным в двоичном виде). Тогда что мы можем сказать о вычислительной сложности ? Понятно, что . И если я не ошибаюсь, удивительные алгоритмы типа «BBP» для вычисления бита с использованием квазилинейного времени и памяти без необходимости вычислять предыдущие биты дают . $n$ $L$ $L\in\mathsf{EXP}$ $n^{th}$ $\pi$ $(\log n)^{O(1)}$ $L\in\mathsf{PSPACE}$

Можем ли мы сделать еще лучше и поместить (скажем) в счетную иерархию? В другом направлении, есть ли какой-либо результат твердости для (даже очень слабый, как -hardness)? $L$ $L$ $\mathsf{TC}^0$

Интересный родственный язык

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

(где снова, записывается в двоичном виде). У нас есть $t$

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

и, следовательно, ; Я был бы чрезвычайно заинтересован, если бы что-нибудь лучшее было известно. $L' \in \mathsf{PSPACE}$

cc.complexity-theory na.numerical-analysis Скотт Ааронсон
источник

(1) Потому что - самое известное трансцендентное число, и о нем известно много. (2) Потому что я хотел конкретный пример. (Меня, конечно, также очень интересовали бы аналогичные вопросы для , и т. Д., В какой бы степени ни отличались ответы.) (3) Потому что для Chaitin's я уже знаю ответ : а именно, вычисление двоичной цифры не вычислимо! (И я предполагаю, что можно привести сокращение, показывающее, что проблема поиска подпоследовательности также неисчислима для ... кто-нибудь знает, как?)

π

$\pi$

e

$e$

\sqrt{2}

$\sqrt{2}$

Ω

$\Omega$

n^{t h}

$n^{th}$

Ω

$\Omega$

Скотт Ааронсон,

@ ScottAaronson, я думаю, что мы можем перебрать все строки длины и спросить, есть ли в языке; это дает все из первых нас бит .

x

$x$

t

$t$

⟨ x, t ⟩

$\langle x, t \rangle$

t

$t$

Ω

$\Omega$

усуль

У меня похожий язык в стиле теории чисел: :-)

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

Марцио Де Биаси

Кстати, я проверил Weihrauch, в конце раздела 7.2 говорится , что п-й бит тригонометрических функций и их обратными могут быть вычислены по времени , используя подписанное -значное представление ( с учетом в сложение и в виде цифры) на компактных подмножествах их домена. ( - сложность двоичного целочисленного умножения.)

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

Ответы:

Хорошо, Джеймс Ли указал мне на эту статью 2011 года Самира Датты и Рамешвара Пратапа, которая доказывает, что мой язык (кодирующий цифры ) находится на четвертом уровне иерархии подсчета ( , спасибо SamiD ниже за то, что он указал на отсутствующий в статье, которую я просто повторил в своем ответе! ). В статье также подробно обсуждается мой вопрос о нижних оценках сложности вычисления двоичных цифр иррациональных чисел, хотя удается лишь доказать очень слабую нижнюю оценку для вычисления двоичных цифр рациональных чисел. Это именно то, что я искал. $L$ $\pi$ $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$ $\mathsf{PP}$

Обновление (3 апреля): Забавное следствие того, что цифры вычислимы в иерархии подсчета, выглядит следующим образом. Предположим, что - это нормальное число (двоичное разложение которого быстро сходится к «эффективно случайному»), и предположим, что (с моделированием, включающим только небольшие полиномиальные издержки). Тогда можно было бы запрограммировать ваш компьютер, чтобы найти, например, первое вхождение полного собрания сочинений Шекспира в двоичном расширении . Если для вас это звучит абсурдно, то, возможно, это следует воспринимать как дополнительное доказательство того, что . :-) $\pi$ $\pi$ $\mathsf{P} = \mathsf{PP}$ $\pi$ $\mathsf{P} \ne \mathsf{PP}$

Скотт Ааронсон
источник

Хорошо, но он говорит, что я должен ждать 5 часов, прежде чем сделать это!

Скотт Ааронсон

Кстати, упомянутая выше статья существенно сводит проблему к и ошибочно цитирует границу как . Самая известная граница в настоящее время как показано здесь: 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