Эквивалентные определения конструктивности времени

13

Мы говорим, что функция f:NN является конструируемой во времени , если существует детерминированная многоленточная машина Тьюринга M которая на всех входах длины n делает не более f(n) шагов, и для каждого существует некоторый вход длина на которой делает точно шагов.n M f ( n )nnMf(n)

Будем говорить , что функция является полной времени конструктивны , если существует детерминированный мульти-машине Тьюринга , что на всех входах длины делает именно шагов ,f:NNn f ( n )Mnf(n)

Q1: существует ли функция, которая является конструируемой во времени и не полностью конструируемой во времени?

Ответ : да (см этот ответ ), если EXPTIMENEXPTIME . Может ли условие «да» быть усилено до ? Можно ли доказать «да»?PNP

Вопрос 2: Изменится ли класс (полностью) зависящих от времени функций, если мы разрешим в определении только 2-лентные машины Тьюринга?

Q3: Каковы «доказуемые» причины полагать, что все приятные функции полностью конструируемы по времени?

Статья
Кодзиро Кобаяши: О доказуемости временной конструктивности функций. Теор. Вычи. Sci. 35: 215-225 (1985)
частично отвечает на вопрос 3. Частичное резюме и обновление этого в этом ответе . Я беру Q3 как ответ.

Исторически понятие счетной функции в реальном времени использовалось вместо (полностью) конструируемой во времени. Смотрите этот вопрос для более.

Дэвид Г
источник
Любопытно - не могли бы вы указать мне ссылку на эти определения? Я не знаком с построимых функциями, и я не могу найти эти определения в Интернете (это также не очевидно для меня, являются ли они эквивалентны , например , в Википедии из них).
Усул
@usul Ссылка: Дж. Э. Хопкрофт, Дж. Д. Уллман. Введение в теорию автоматов, языков и вычислений. Серия Аддисона-Уэсли в области компьютерных наук, 1979 г. Такое же определение можно найти здесь: cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html
Дэвид Дж.

Ответы:

5

В последние несколько дней я много думал о (полностью) конструируемых во времени функциях, и я представлю то, что узнал, ответив на вопросы 1 и 3. Q2 кажется слишком сложным.

Q3:

Кобаяши в своей статье (ссылка на вопрос) доказал, что функция , для которой существует ϵ > 0 st f ( n ) ( 1 + ϵ ) n , вполне конструируема по времени, если она вычислимый в O ( F ( N ) ) времени. (обратите внимание, что не имеет значения, является ли вход или выход унарным / двоичным, поскольку мы можем преобразовать эти два представления в линейное время). Это делает следующие функции полностью зависящими от времени: 2 n ,f:NNϵ>0f(n)(1+ϵ)nO(f(n))2n , н ! , n log n , все многочлены p над N st p ( n ) ( 1 + ϵ ) n ... Кобаяши также полностью построил по времени для некоторых функций, растущих медленнее, чем ( 1 + ϵ ) n , например n + log n q для q Q + ...22nn!nlognpNp(n)(1+ϵ)n(1+ϵ)nn+lognqqQ+

Чтобы продолжить примеры полного времени конструктивны функций, можно доказать , что если и F 2 полностью времени конструктивны, то е 1 + ф 2 , е 1 е 2 , е е 2 1 и е 1е 2 являются также полностью конструируемым во времени (последнее следует непосредственно из теоремы 3.1 в Кобаяси). Это в целом убеждает меня в том, что многие полезные функции действительно могут быть построены по времени.f1f2f1+f2f1f2f1f2f1f2

Удивительно, что Кобаяши не видел способа полностью доказать время-конструкцию (хорошей) функции (и я тоже).nlogn

Давайте также прокомментируем определение из статьи в Википедии : функция является конструируемой во времени, если существует машина Тьюринга M, которая при заданной строке 1 n выдает f ( n ) за O ( f ( n ) ) времени. fM1nf(n)O(f(n)) Мы видим, что это определение эквивалентно нашему определению вполне временной конструкции для функций .f(n)(1+ϵ)n

Q1:

На этот вопрос есть действительно интересный ответ. Я утверждаю , что если все время-построимо функции полностью во времени конструктивны, то . Для доказательства возьмем произвольную задачу L N E X P - T I M E , L { 0 , 1 } . Тогда существует k N , st LEXPTIME=NEXPTIMELNEXPTIMEL{0,1}kNLможет быть решена с помощью NDTM за 2 n k - 1 шагов. Для простоты можно предположить, что на каждом шаге M переходит не более чем в два разных состояния. Теперь определим функцию f ( n ) = { 8 n + 2 if  ( first k √)M2nk1M

f(n)={8n+2if (first logn+1k bits of bin(n))L8n+1else

Я утверждаю, что конструируется во времени. Рассмотрим следующую детерминированную машину Тьюринга T :fT

  • на входе длины n вычисляет ( сначала k wnзаO(n)время(first logn+1k bits of bin(n))O(n)
  • затем он моделирует для этих битов, где биты w определяют, какой (ранее недетерминированный) выбор выбрать.Mw
  • принять, если .(M accepts using choices given by w)

Обратите внимание, что длины ( = n ) достаточно, чтобы определить все недетерминированные варианты, так как M на входе ( сначала k w=nMсоставляет не болеепшагов.(first logn+1k bits of bin(n))n

Мы можем заставить работать не более 8 n + 1 шагов. Теперь следующая машина Тьюринга доказывает, что f конструируется во времени:T8n+1f

  • на входе длины n запустите T и подсчитайте количество шагов параллельно, чтобы было выполнено ровно 8 n шагов.wnT8n
  • если отклонен или будет отклонен на следующем шаге, перейдите в состояние остановки на следующем шаге. Иначе, сделайте еще один шаг и затем перейдите в состояние остановки.T

Now suppose that f is fully time-constructible. We will prove that this leads to EXPTIME=NEXPTIME.

The following algorithm solves L:

  • on input x, let n be the number with binary representation x000 (|x|k1 zeros). It follows that x=(first logn+1k bits of bin(n)).
  • compute f(n) in time f(n) and check whether it is divisible by 2.

This algorithm runs in exponential time and solves L. Since LNEXPTIME was arbitrary, EXPTIME=NEXPTIME.

David G
источник
4
Very nice! [padding to make the comment box happy]
Emil Jeřábek 3.0
1
A very similar idea to the one presented in the answer to the question Q1 is also used here.
David G