При каких обстоятельствах

16

Предположим, что для каждого ϵ>0 существует машина Тьюринга Mϵ которая определяет язык L во времени O(na+ϵ) . Существует ли единственный алгоритм, определяющий L во времени O(na+o(1)) ? (Здесь член o(1) измеряется через n , длину ввода.)

Имеет ли значение, если алгоритмы Mϵ вычислимы или эффективно вычисляются в терминах ϵ ?

Мотивация: во многих доказательствах легче построить алгоритмы времени O(na+ϵ) чем ограничивающий алгоритм O(na+o(1)) . В частности, вам нужно ограничить постоянный член в O(na+ϵ) чтобы перейти к пределу O(na+o(1)) . Было бы неплохо, если бы был какой-то общий результат, который вы можете вызвать, чтобы перейти к пределу напрямую.

Дэвид Харрис
источник

Ответы:

10

Вопрос аналогичен вопросам о конструктивном существовании предела последовательности (конструктивных) объектов. Обычно, если вы можете достаточно равномерно построить эти объекты (здесь ), тогда вы можете показать существование предела конструктивно.Mϵ

Например, предположим, что у нас есть TM который выполняет M | к | - 1 на x и его время выполнения равно O ( n a + | k | - 1 ) + O ( | k | ) (здесь границы также равномерны, например, что-то типа O ( 2 k . N a + | k | - 1 )N(k,x)M|k|1xO(na+|k|1)+O(|k|)O(2k.na+|k|1)не будет работать). Затем мы можем объединить этот равномерный симулятор с функцией чтобы получить машину N ( x , x ), которая работает за время O ( n a + o ( 1 ) ) .(k,x)xN(x,x)O(na+o(1))

PS: немного неоднозначно из-за вложенности асимптотических обозначений, я интерпретирую это как n a + o ( 1 ) . Кроме того, мы должны быть не слишком маленьким, например , по меньшей мере , 1 .O(na+o(1))na+o(1)a1

Кава
источник
8

Вы можете использовать универсальный алгоритм поиска Левина. Предположим, что вы можете каким-то образом перечислить последовательность алгоритмов решающих L , каждый из которых выполняется за время C k n a + 1 / k . Алгоритм работает Левина в время Т ( п ) D к п + 1 / к для каждых к , где Д к является константой , зависящей от С к . Таким образом, для каждого k , τ ( n ) AkLCkna+1/kT(n)Dkna+1/kkDkCkk Дляϵ>0выберитеk=2/ϵи пустьN=D 2 / ϵ k. Тогда приnN,τ(n)ϵ. Поэтомуτ(n)0, и мы получаем, что алгоритм Левина работает за времяna+τ(n)=na+

τ(n)logT(n)lognalogDk+(a+1/k)lognlogna=logDklogn+1k.
ϵ>0k=2/ϵN=Dk2/ϵnNτ(n)ϵτ(n)0 .na+τ(n)=na+o(1)
Юваль Фильмус
источник
Если я понимаю алгоритм Левина, это относится только к алгоритмам поиска. Этот алгоритм будет работать, чтобы инвертировать функцию , где f может быть вычислена за время O ( n o ( a ) ) . ffO(no(a))
Дэвид Харрис
Я не предлагаю использовать сам алгоритм Левина, просто идею запустить все алгоритмы параллельно, используя ласточкин хвост, таким образом, что каждый из них замедляется только мультипликативным фактором. Ak
Юваль Фильмус
@ Юваль, когда ты согласуешь все алгоритмы, как ты решаешь, какой ответ принять? В задаче поиска вы можете проверить каждый предполагаемый вывод, но в целом это невозможно.
Дэвид Харрис
AkL