NTIME (f) подмножество DSPACE (f)

Поскольку вопрос гласит, как мы можем доказать, что ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Кто-нибудь может указать мне на доказательство или изложить его здесь? Спасибо!

complexity-theory time-complexity space-complexity gdiazc
источник

Я думаю, что есть мульт. константы прячутся там. Вы можете доказать, что . Просто перечислите все возможные недетерминированные предположения алгоритма и запустите ваш алгоритм с этими предположениями. Принять, если одна из догадок приводит к принимающему состоянию.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Игорь Шинкарь

Почему бы не сделать это ответом?

Юваль Фильмус

@IgorShinkar Существуют различные результаты, такие как теорема о линейном ускорении и теорема о сжатии ленты, которые говорят, что вы можете избавиться от этих констант в «большинстве» обстоятельств. Линейное ускорение говорит, что для любого ; Сжатие ленты говорит, что , опять же для любого .

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

Дэвид Ричерби

Ответы:

Вот расширенная версия комментария Игоря Шинкара. Самый простой способ для моделирования недетерминированной машины, работающей во времени и пространстве использует пространство . Мы перечисляем все возможные броски монет, моделируя оригинальную машину на каждом из них; для этого требуется пространство для хранения бросков монет и место для моделирования реальной машины. Здесь есть небольшая трудность: когда броски монет «читаются» (оригинальной) машиной, нам нужно как-то отметить, где мы находимся в последовательности бросков монет; мы можем использовать дополнительный бит за бросок монеты. Вероятно, можно оптимизировать это еще дальше. $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ $s(n)$

Если мы будем осторожны, мы сможем получить что-то еще лучше, так как при каждом запуске программы общее количество брошенных монет и общее использованное пространство складываются не более чем в . Я подозреваю, что можно запустить симуляцию в пространстве. Возможно, для этого нам понадобится что-то вроде . $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Как упоминает Игорь, обычно классы, ограниченные ресурсами, определяются только "до больших O", поэтому результат, который использует пространство , все еще находится в . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Юваль Фильмус
источник