Есть ли какое-нибудь известное вычислимое трансцендентное число такое, что его Эта цифра вычисляется за полиномиальное время, но не в ?
cc.complexity-theory
comp-number-theory
XL _At_Here_There
источник
источник
Ответы:
Вот конструкция такого числа. Вы можете поспорить, означает ли это, что такое число "известно".
Возьми любую функциюf от N в {1,2,…,8} где n эта цифра не вычисляется в O(n) время. Такая функция существует, например, с помощью обычной техники диагонализации. истолковыватьf(n) как n десятичная цифра некоторого вещественного числа α , Теперь для каждогоn формы 22k , k≥1 измените цифры α в позициях n,n+1,…,3n в 0 «S. Полученное числоβ очевидно, сохраняет свойство, которое n эта цифра не вычисляется в O(n) время, но имеет бесконечно много очень хороших приближений рациональными, скажем, на заказ O(q−3) в форме p/q , Тогда по теореме Ротаβ не может быть алгебраическим. (Это не рационально, потому что оно имеет сколь угодно длинные блоки0 Выделено ненулевыми значениями с обеих сторон.)
источник
В целом, для любой постояннойk≥1 есть трансцендентные числа, вычисляемые за полиномиальное время, но не во времени O(nk) ,
Во-первых, по теореме иерархии времени существует языкL0∈E не вычисляется во времени O(2kn) , Мы можем предположитьL⊆{0,1}∗ и мы также можем предположить, что все строки w∈L иметь длину, кратную 3 ,
Во-вторых, пустьL1 быть унарной версией L0 , Для определенности, для любогоw∈{0,1}∗ , позволять N(w) обозначает целое число, двоичное представление которого 1w , и положи L1={aN(w):w∈L0} , затемL1∈P , но L1 не вычисляется во времени O(nk) , Более того,L1 имеет следующее свойство: для любого m , L1 не содержит никаких an такой, что 23m+1≤n<23m+3 ,
В-третьих, пусть
затемα вычисляется за полиномиальное время, так как мы можем вычислить его n биты, проверяя, a,a2,…,an находятся в L1 , По той же причине, это не вычисляется во времениO(nk) как n -ый бит определяет an∈L1 ,
Для любойm , позволять
источник