Границы времени выполнения разрешимы для чего-нибудь нетривиального?

14

Задача   Дана машина Тьюринга которая знает время выполнения O ( g ( n ) ) относительно длины ввода n , является временем выполнения M O ( f ( n ) )MО(грамм(N))NMО(е(N)) ?

Разрешима ли указанная выше проблема для некоторых нетривиальных пар и f ? Решение тривиально, если g ( n ) O ( f ( n ) ) .граммеграмм(N)О(е(N))

Это связано с проблемой Разрешаемы ли границы времени выполнения в P? (ответ: нет) . Из ответа Виолы можно вывести , что если и f ( n ) O ( g ( n ) ), то проблема неразрешима.е(N)о(N)f(n)O(g(n))

Требование , что потому , что М ' в доказательство необходимости Виолы O ( п ) время , чтобы найти свой входной размер. Таким образом, доказательство Виолы не может работать, когда f ( n ) = 1 .f(n)o(n)MO(n)f(n)=1

Было бы интересно, если бы мы могли выбрать время выполнения алгоритмов сублинейного времени. Особый случай - когда мы имеем произвольные и f ( n ) = 1 .g(n)f(n)=1

Чао Сюй
источник
Поскольку вопрос, на который вы ссылаетесь, был очень хорошо принят на CSTheory, вы можете захотеть пометить миграцию позже.
Юхо

Ответы:

5

Вот несколько замечаний, которые могут иметь отношение к теме:

  1. Кобаяши доказал, что ТМ, работающая во времени принимает обычный язык (и, следовательно, работает во времени O ( n ) ); недавно это было распространено на недетерминированные ТМ ( Тадаки, Ямаками и Лин ).o(nlogn)O(n)
  2. Машины, работающие за время самом деле работают за постоянное время (рассмотрим любой n, для которого время выполнения меньше n ; добавление символов в конец не влияет на TM).o(n)nn
Юваль Фильмус
источник
1
Стоит отметить, что 1. справедливо только для ТМ с одной лентой
Сашо Николов