Для каждой вычислимой функции

19

Для каждой вычислимой функции существует ли задача, которая может быть решена в лучшем случае за время или существует вычислимая функция такая, что любая задача, которая может быть решена в может также быть решено в время? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Этот вопрос возник в моей голове вчера. Я думал об этом немного сейчас, но не могу понять это. Я действительно не знаю, как я Google для этого, поэтому я спрашиваю здесь. Вот что я придумала:

Сначала я подумал, что ответ «да»: для каждой вычислимой функции $f$ проблема «Вывести точек» (или создать строку с точками или чем-либо еще), очевидно, не может быть решена в время. Таким образом, нам нужно только показать, что это может быть решено за время. Нет проблем, просто возьмите следующий псевдокод: $f(n)$ $f(n)$ $o(f(n))$ $O(f(n))$

x = f(n)
for i from 1 to x:
    output(".")

Понятно, что этот алгоритм решает поставленную задачу. И время его выполнения явно в , поэтому проблема решена. Это было легко, правда? Кроме нет, это не потому, что вы должны учитывать стоимость первой строки. Время выполнения вышеупомянутого алгоритма только в если время, необходимое для вычисления находится в . Очевидно, что это не так для всех функций ¹ . $\Theta(f(n))$ $\Theta(f(n))$ $f(n)$ $O(f(n))$

Так что такой подход никуда меня не привел. Я был бы благодарен всем, кто указал мне правильное направление, чтобы понять это должным образом.

¹ Рассмотрим, например, функцию . Ясно, что , но нет алгоритма, который вычисляет за времени. $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$ $O(p(n)) = O(1)$ $p$ $O(1)$

complexity-theory sepp2k
источник

1

Я не думаю, что ваши два утверждения в ваших первых абзацах обязательно противоположны друг другу: что, если у вас есть такое

, что существует некоторая проблема, которая может быть решена в

, а не в

ни во время

?

f

$f$

O (f (n))

$O(f(n))$

o (f (n))

$o(f(n))$

Θ (f (n))

$\Theta(f(n))$

Алекс тен Бринк

@ Алекс Это хорошая мысль, я не учел это.

sepp2k

13

По теореме Гэпа (используя формулировку отсюда , ищите «пробел»), для любой вычислимой неограниченной функции существует некоторая возрастающая (на самом деле, сколь угодно большая) вычислимая функция такая, что . $g : \mathbb{N} \rightarrow \mathbb{N}$ $f : \mathbb{N} \rightarrow \mathbb{N}$ $DTIME(f(n)) = DTIME(g(f(n))$

Это отвечает на ваш вопрос тем, что существует такое (на самом деле бесконечное множество): для любой вычислимой функции такой, что , существует некоторая возрастающая функция такая что все задачи, разрешимые в время также разрешимо за время. Обратите внимание, что $f$ $g$ $g = o(n)$ $f$ $O(f(n))$ $O(g(f(n)) = o(f(n))$ $f$ не обязательно конструируемый во времени - для случая, который конструируем во времени, смотрите ответ @RanG.

В формулировке Википедии (которая требует, чтобы ), тогда становится вашим примером, а должно быть (так что вы идете наоборот - 'проблемы, решаемые в также разрешимы в '- интересная часть). $g(x) \geq x$ $g \circ f$ $f$ $\omega(n)$ $O(g(f(n))$ $O(g(n))$

В статье Википедии не отмечается, что увеличивается и на самом деле может быть сколь угодно большим (например, ). В статье , что и доказывает теорему разрыва делает упоминание и доказать это (см здесь , например). $f$ $f(n) \geq g(n)$

Алекс тен Бринк
источник

может быть

? Разве не требуется, чтобы

? Ваше утверждение все еще верно, но доказательство идет другим путем, верно?

g

$g$

o (n)

$o(n)$

g (x) \geq x

$g(x)\ge x$

Ран Г.

@RanG. Обновленный, чтобы дать доказательство для обеих формулировок (я использовал формулировку в статье) :)

Алекс тен Бринк

«для любой вычислимой функции g такой, что g = o (n), существует некоторая функция f, такая, что все задачи, решаемые за время O (f (n)), также разрешимы за O (g (f (n)) = o ( f (n)) time "Что если все f, которые существуют для этого g, находятся в O (1)? Тогда O (g (f (n)) все еще равно O (1) и, следовательно, не o (1).

sepp2k

@ sepp2k: хороший улов, это действительно проблема, как сформулировано. Я обновил свой ответ.

Алекс тен Бринк

12

Для любой вычислимой функции существует ли задача, которая может быть решена в лучшем случае за время или существует вычислимая функция такая, что любая задача, которая может быть решена в также может быть решенным в время? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Если является конструируемой по времени функцией , то теорема об иерархии времени говорит, что существуют проблемы, которые требуют времени и не могут быть решены за время $f$ $O(f(n))$ . В частности, $o\left (\frac{f(n)}{\log(f(n))}\right )$

DTIME (o (\frac{f (n)}{\log (f (n))})) ⊊ DTIME (f (n))

$\text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$

Это учитывает только решение проблем и не учитывает время, необходимое для генерации выходных данных.

Ран Г.
источник

Прав ли я, если предположить, что если мы рассмотрим не конструируемые во времени функции, то ответ на мой вопрос будет «нет»? Или, соответственно: если функция

не может быть построена по времени и, следовательно, нет машины Тьюринга, которая останавливается после шагов

, означает ли это, что также нет машины Тьюринга, которая останавливается после шагов

? Потому что из этого тривиально следует, что ответ на мой вопрос - нет.

f

$f$

f (n)

$f(n)$

Θ (f (n))

$\Theta(f(n))$

sepp2k

По-разному. Предположим, что

не конструируется во времени, но может быть ограничено некоторой другой функцией

которая конструируется во времени.

и все еще существуют проблемы, которые можно решить за время

но не намного меньше этого.

f

$f$

g

$g$

f = Θ (g)

$f=\Theta(g)$

O (f)

$O(f)$

Ран Г.

и используя несколько ленточных TM, вы можете улучшить результат от

до

.

o (\frac{f (n)}{\lg f (n)})

$o(\frac{f(n)}{\lg f(n)})$

o (f (n))

$o(f(n))$

Каве

3

Я попытаюсь представить что-то вроде основы в надежде, что она даст более глубокое понимание.

Когда вы добираетесь до чего-то такого фундаментального, везде возникают неожиданные ловушки. Например: что значит «решить» проблему? Часто в компьютерных науках мы рассматриваем только вариант «принятия решения», в котором нам дают ввод, и нам нужно только вывести True или False. Вы концентрируетесь на проблеме «функции».

Если вы рассматриваете нотацию O (f (n)) как попытку отловить, сколько «работы» необходимо для решения проблемы, использование решения вместо функции (где требуется вывод) кажется более подходящим, поскольку вы четко отделяете вычисления от форматирования вывода ,

Я не думаю, что это ответит на ваш вопрос, но вас это может заинтересовать: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Также будьте осторожны с теоремой ускорения .

agorenst
источник

Для каждой вычислимой функции

Ответы: