Мы говорим, что функция является конструируемой во времени , если существует детерминированная многоленточная машина Тьюринга которая на всех входах длины делает не более шагов, и для каждого существует некоторый вход длина на которой делает точно шагов.n M f ( n )
Будем говорить , что функция является полной времени конструктивны , если существует детерминированный мульти-машине Тьюринга , что на всех входах длины делает именно шагов ,n f ( n )
Q1: существует ли функция, которая является конструируемой во времени и не полностью конструируемой во времени?
Ответ : да (см этот ответ ), если . Может ли условие «да» быть усилено до ? Можно ли доказать «да»?
Вопрос 2: Изменится ли класс (полностью) зависящих от времени функций, если мы разрешим в определении только 2-лентные машины Тьюринга?
Q3: Каковы «доказуемые» причины полагать, что все приятные функции полностью конструируемы по времени?
Статья
Кодзиро Кобаяши: О доказуемости временной конструктивности функций. Теор. Вычи. Sci. 35: 215-225 (1985)
частично отвечает на вопрос 3. Частичное резюме и обновление этого в этом ответе . Я беру Q3 как ответ.
Исторически понятие счетной функции в реальном времени использовалось вместо (полностью) конструируемой во времени. Смотрите этот вопрос для более.
Ответы:
В последние несколько дней я много думал о (полностью) конструируемых во времени функциях, и я представлю то, что узнал, ответив на вопросы 1 и 3. Q2 кажется слишком сложным.
Q3:
Кобаяши в своей статье (ссылка на вопрос) доказал, что функция , для которой существует ϵ > 0 st f ( n ) ≥ ( 1 + ϵ ) n , вполне конструируема по времени, если она вычислимый в O ( F ( N ) ) времени. (обратите внимание, что не имеет значения, является ли вход или выход унарным / двоичным, поскольку мы можем преобразовать эти два представления в линейное время). Это делает следующие функции полностью зависящими от времени: 2 n ,е: N → N ϵ>0 f(n)≥(1+ϵ)n O(f(n)) 2n , н ! , n ⌊ log n ⌋ , все многочлены p над N st p ( n ) ≥ ( 1 + ϵ ) n ... Кобаяши также полностью построил по времени для некоторых функций, растущих медленнее, чем ( 1 + ϵ ) n , например n + ⌊ ⌊ log n ⌋ q ⌋ для q ∈ Q + ...22n n! n⌊logn⌋ p N p(n)≥(1+ϵ)n (1+ϵ)n n+⌊⌊logn⌋q⌋ q∈Q+
Чтобы продолжить примеры полного времени конструктивны функций, можно доказать , что если и F 2 полностью времени конструктивны, то е 1 + ф 2 , е 1 е 2 , е е 2 1 и е 1 ∘ е 2 являются также полностью конструируемым во времени (последнее следует непосредственно из теоремы 3.1 в Кобаяси). Это в целом убеждает меня в том, что многие полезные функции действительно могут быть построены по времени.f1 f2 f1+f2 f1f2 ff21 f1∘f2
Удивительно, что Кобаяши не видел способа полностью доказать время-конструкцию (хорошей) функции (и я тоже).⌊nlogn⌋
Давайте также прокомментируем определение из статьи в Википедии : функция является конструируемой во времени, если существует машина Тьюринга M, которая при заданной строке 1 n выдает f ( n ) за O ( f ( n ) ) времени.f M 1n f(n) O(f(n)) Мы видим, что это определение эквивалентно нашему определению вполне временной конструкции для функций .f(n)≥(1+ϵ)n
Q1:
На этот вопрос есть действительно интересный ответ. Я утверждаю , что если все время-построимо функции полностью во времени конструктивны, то . Для доказательства возьмем произвольную задачу L ∈ N E X P - T I M E , L ⊆ { 0 , 1 } ∗ . Тогда существует k ∈ N , st LEXP−TIME=NEXP−TIME L∈NEXP−TIME L⊆{0,1}∗ k∈N L может быть решена с помощью NDTM за 2 n k - 1 шагов. Для простоты можно предположить, что на каждом шаге M переходит не более чем в два разных состояния. Теперь определим функцию
f ( n ) = { 8 n + 2 if ( first ⌊ k √)M 2nk−1 M
Я утверждаю, что конструируется во времени. Рассмотрим следующую детерминированную машину Тьюринга T :f T
Обратите внимание, что длины ( = n ) достаточно, чтобы определить все недетерминированные варианты, так как M на входе ( сначала ⌊ k √w =n M составляет не болеепшагов.(first ⌊⌊logn⌋+1−−−−−−−−−√k⌋ bits of bin(n)) n
Мы можем заставить работать не более 8 n + 1 шагов. Теперь следующая машина Тьюринга доказывает, что f конструируется во времени:T 8n+1 f
Now suppose thatf is fully time-constructible. We will prove that this leads to EXP−TIME=NEXP−TIME .
The following algorithm solvesL :
This algorithm runs in exponential time and solvesL . Since L∈NEXP−TIME was arbitrary, EXP−TIME=NEXP−TIME .
источник