Является ли

12

Определите как класс языков, которые могут быть приняты машиной (множественной) Тьюринга за время f ( n ) + 1 . (« + 1 » просто для упрощения обозначений и предотвращения путаницы.) Обратите внимание, что вокруг f ( n ) + 1 нет O ( ⋅ ) .DTяMЕ(е(N))е(N)+1+1О(⋅)е(N)+1

Правда ли, что ?DTIME(n)=DTIME(2n)

Используя теорему о линейном ускорении , мы можем доказать, что , но можем ли мы достичь n ?DTIME(2n)=DTIME(1.01n)n

Кажется, что язык палиндромов в ; для связанных тем см . сообщение в блоге Липтона о строковых алгоритмахDTIME(n)

cc.complexity-theory time-complexity turing-machines time-hierarchy domotorp
источник
3
В « Детерминированных машинах Тьюринга в диапазоне между реальным и линейным временем » я обнаружил: если и r ′ ∈ o ( r ), то D T I M E ( n + r ′ ) ⊂ D Т Я М Е ( п + г )r∈T−1(DTM)r′∈o(r)DTIME(n+r′)⊂DTIME(n+r)
Марцио Де Бязи
Ницца, кажется, именно то, что я искал. Вы хотите преобразовать это в ответ?
Domotorp
1
интересный вопрос, но возражать против переопределения стандартного класса сложности DTIME нестандартным способом, предлагаю вам хотя бы назвать его чем-то вроде DTIME ', чтобы избежать путаницы
vzn
Эта статья может быть полезной. [Розенберг 67] Определенные
zZzZzZ

Ответы:

12

Из комментария:

В « Детерминированных машинах Тьюринга в диапазоне между реальным и линейным временем » я обнаружил:

... если и r ′ ∈ o ( r ), то D T I M E ( n + r ′ ) ⊂ D T I M E ( n + r ) ...р∈T-1(DTM)р'∈о(р)DTяMЕ(N+р')⊂DTяMЕ(N+р)

Марцио де Биаси
источник
5
Что такое ? T-1(DTM)
Эмиль Йержабек
1
является обратным возрастающей, неограниченнойвремени конструктивны функции F ( ∀ C ∈ N , ∃ п 0 , с ' ∈ N - й ∀ п ≥ п 0 мы имеем гр п ( п ) ≤ F ( c ′ n ) ). Вы можете заменить его честной сублинейной функцией. T-1(DTM)е∀с∈N,∃N0,с'∈N∀N≥N0се(N)≤е(с'N)
Марцио Де Биаси