Любое вычислимое трансцендентное число, которое вычислимо за время P, но не

9

Есть ли какое-нибудь известное вычислимое трансцендентное число такое, что его nЭта цифра вычисляется за полиномиальное время, но не в O(n)?

XL _At_Here_There
источник
2
Это все еще не имеет смысла. Вы имеете в виду «... но не вовремяO(n)", или что?
Эмиль Йержабек
Я имею в виду время P, а не в O(n), Я не уверен, что мой английский неправильный или ваш, в любом случае, спасибо за ваш комментарий.
XL _At_Here_There
2
Если автору удается сформулировать этот вопрос на удобочитаемом английском языке, то это может быть связано с гипотезой Хартманиса-Стернса: каждое действительное число, вычисляемое многоканальной машиной Тьюринга в реальном времени, является либо трансцендентным, либо рациональным.
Gamow
@ Да, верно ,, но это исключает случай гипотезы Хартманиса-Стернса.
XL _At_Here_There
2
Я пытался сделать это понятным, но это все еще не очень ясно. Вы имеете в виду не известно, чтобы быть вычисляемым вO(n)или доказуемо не вычислимо в O(n)? Какая модель вычислений: одиночная или многолучевая машина Тьюринга или что-то еще?
Сашо Николов

Ответы:

19

Вот конструкция такого числа. Вы можете поспорить, означает ли это, что такое число "известно".

Возьми любую функцию f от N в {1,2,,8} где nэта цифра не вычисляется в O(n)время. Такая функция существует, например, с помощью обычной техники диагонализации. истолковыватьf(n) как nдесятичная цифра некоторого вещественного числа α, Теперь для каждогоn формы 22k, k1измените цифры α в позициях n,n+1,,3n в 0«S. Полученное числоβ очевидно, сохраняет свойство, которое nэта цифра не вычисляется в O(n) время, но имеет бесконечно много очень хороших приближений рациональными, скажем, на заказ O(q3)в форме p/q, Тогда по теореме Ротаβне может быть алгебраическим. (Это не рационально, потому что оно имеет сколь угодно длинные блоки0Выделено ненулевыми значениями с обеих сторон.)

Джеффри Шаллит
источник
12

В целом, для любой постоянной k1есть трансцендентные числа, вычисляемые за полиномиальное время, но не во времени O(nk),

Во-первых, по теореме иерархии времени существует язык L0E не вычисляется во времени O(2kn), Мы можем предположитьL{0,1}и мы также можем предположить, что все строки wL иметь длину, кратную 3,

Во-вторых, пусть L1 быть унарной версией L0, Для определенности, для любогоw{0,1}, позволять N(w) обозначает целое число, двоичное представление которого 1w, и положи L1={aN(w):wL0}, затемL1P, но L1 не вычисляется во времени O(nk), Более того,L1 имеет следующее свойство: для любого m, L1 не содержит никаких an такой, что 23m+1n<23m+3,

В-третьих, пусть

α={2n:anL1}.
(Я предполагаю, что здесь речь идет о вычислении чисел в двоичном формате. Если нет, то 2 выше можно заменить на любую нужную базу, это не важно.)

затем α вычисляется за полиномиальное время, так как мы можем вычислить его n биты, проверяя, a,a2,,an находятся в L1, По той же причине, это не вычисляется во времениO(nk)как n-ый бит определяет anL1,

Для любой m, позволять

p={223m+1n:nL1,n<23m+1}=α223m+1,
а также q=223m+1, затем
|αpq|223m+3=q4.
Таким образом, α имеет меру иррациональности как минимум 4следовательно, он является трансцендентным по теореме Рота .
Эмиль Йержабек
источник
2
Хм, я вижу, что меня зачерпнули. Я все равно оставлю ответ, так как он может быть полезен для кого-то.
Эмиль Йержабек
3
Я выбрал пост Джеффри в качестве ответа на вопрос, так как его ответ опубликован ранее.
XL _At_Here_There
6
Да. В следующий раз я напомню себе, что не стоит тратить время и силы на написание подробного ответа со всеми техническими деталями, так как вместо этого гораздо важнее опубликовать сообщение несколькими минутами ранее.
Эмиль Йержабек
3
: D отлично! Надеюсь, мы сможем получить больше тем.
XL _At_Here_There