Теорема временной иерархии

Если у вас больше времени, машина Тьюринга может решить больше задач

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

Теорема иерархии времени для детерминированных многоленточных машин Тьюринга была впервые доказана Ричардом Э. Стернсом и Юрисом Хартманисом в 1965 году. был улучшен год спустя, когда Хенни и Ричард Э. Стернс повысили эффективность универсальной машины Тьюринга. В соответствии с теоремой для каждого детерминированного ограниченного по времени класса сложности существует строго больший ограниченный по времени класс сложности, и поэтому ограниченная по времени иерархия классов сложности не разрушается полностью. Точнее, теорема об иерархии времени для детерминированных машин Тьюринга утверждает, что для всех функций, которые могут быть построены во времени, f (n),

$DTIME\; (o\; (f\; (n)\; log\; \; f\; (n)))\; ⊊\; DTIME\; (е\; (п))\; \{\backslash \; Displaystyle\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; влево\; (о\; \backslash \; влево\; (\{\backslash \; гидроразрыва\; \{f\; (n)\}\; \{\backslash \; log\; f\; (n)\}\}\; \backslash \; вправо)\; \backslash \; вправо)\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{DTIME\}\}\; (f\; (n))\}$.

Теорема иерархии времени для недетерминированных машин Тьюринга была первоначально доказана Стивеном Куком в 1972 году. его нынешняя форма с помощью комплексного доказательства Джоэла Сейфераса, Майкла Фишера и Альберта Мейера в 1978 году. Наконец, в 1983 году Станислав Жак достиг того же результата с помощью простого доказательства, которому преподают сегодня. Теорема об иерархии времени для недетерминированных машин Тьюринга утверждает, что если g (n) - функция, которую можно построить во времени, и f (n + 1) = o (g (n)), то

$NTIME\; (\; е\; (п))\; ⊊\; NTIME\; (g\; (n))\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{NTIME\}\}\; (f\; (n))\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{NTIME\}\}\; (g\; (n))\}$.

Аналогичный теоремы для пространства - это теоремы об иерархии пространства. Подобная теорема не известна для классов вероятностной сложности с ограничением по времени, если только класс не имеет одного бита advice.

• 1 Предпосылки
• 2 Обзор доказательства
• 3 Детерминированная теорема об иерархии времени
  • 3.1 Утверждение
  • 3.2 Доказательство
  • 3.3 Расширение
• 4 Теорема о недетерминированной иерархии времени
• 5 Последствия
• 6 См. Также
• 7 Ссылки

Обе теоремы используют понятие функции, построенной по времени. Функция A $f:\; N\; \to \; N\; \{\backslash \; displaystyle\; f:\; \backslash \; mathbb\; \{N\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{N\}\}$конструируется во времени, если существует детерминированный машина Тьюринга такая, что для каждого $n\; \in \; N\; \{\backslash \; displaystyle\; n\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}$, если машина запускается с вводом n единиц, она будет остановка ровно после f (n) шагов. Все полиномы с неотрицательными целыми коэффициентами могут быть построены по времени, как и экспоненциальные функции, такие как 2.

Нам нужно доказать, что некоторый временной класс TIME (g (n)) строго больше, чем некоторый временной класс TIME (f (n)). Мы делаем это, создавая машину, которая не может быть в TIME (f (n)), с помощью диагонализации. Затем мы показываем, что машина находится в ВРЕМЕНИ (g (n)), используя симулятор машины.

Утверждение

Теорема временной иерархии. Если f (n) - временная функция, то существует проблема решения, которая не может быть решена в наихудшем детерминированном времени f (n), но может быть решена в наихудшем детерминированном случае. время f (n). Другими словами,

$D\; T\; I\; M\; E\; (f\; (n))\; ⊊\; D\; T\; I\; M\; E\; (f\; (n)\; 2).\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{DTIME\}\}\; (f\; (n))\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; left\; (f\; (n)\; ^\; \{2\}\; \backslash \; right).\}$

Примечание 1. f (n) не меньше n, поскольку меньшие функции никогда не могут быть построены во времени..

Примечание 2. В более общем плане можно показать, что если f (n) конструктивно во времени, то

$DTIME\; (o\; (f\; (n)\; журнал\; \; f\; (n)))\; ⊊\; DTIME\; (f\; (n)).\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; left\; (о\; \backslash \; left\; (\{\backslash \; frac\; \{f\; (n)\}\; \{\backslash \; log\; f\; (n)\}\}\; \backslash \; right)\; \backslash \; right)\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; left\; (f\; (n)\; \backslash \; right).\}$

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

$o\; (n\; 2\; log\; \; n\; 2).\; \{\backslash \; displaystyle\; o\; \backslash \; left\; (\{\backslash \; frac\; \{n\; ^\; \{2\}\}\; \{\backslash \; log\; \{n\; ^\; \{2\}\}\}\}\; \backslash \; right).\}$

Доказательство

Мы включаем сюда доказательство того, что DTIME (f (n)) - это строгое подмножество DTIME (f (2n + 1)), поскольку оно проще. См. Внизу этого раздела информацию о том, как распространить доказательство на f (n).

Чтобы доказать это, мы сначала определим язык следующим образом:

$H\; f\; =\; \{([M],\; x)\; |\; M\; принимает\; x\; за\; f\; (|\; x\; |)\; шагов\}.\; \{\backslash \; displaystyle\; H\_\; \{f\}\; =\; \backslash \; left\; \backslash \; \{([M],\; x)\; \backslash \; |\; \backslash \; M\; \backslash \; \{\backslash \; text\; \{принимает\}\}\; \backslash \; x\; \backslash \; \{\backslash \; text\; \{in\}\}\; \backslash \; f\; (|\; x\; |)\; \backslash \; \{\; \backslash \; text\; \{steps\}\}\; \backslash \; right\; \backslash \}.\}$

Здесь M - детерминированная машина Тьюринга, а x - ее вход (начальное содержимое ее ленты). [M] обозначает вход, который кодирует машину Тьюринга M. Пусть m будет размером кортежа ([M], x).

Мы знаем, что мы можем определить принадлежность H f с помощью детерминированной машины Тьюринга, которая сначала вычисляет f (| x |), а затем записывает строку из нулей этой длины, а затем использует эту строку нулей в качестве «часов» или «счетчика» для имитации M для максимального количества шагов. На каждом этапе имитирующей машине необходимо просмотреть определение M, чтобы решить, каким будет следующее действие. Можно с уверенностью сказать, что для этого требуется не более f (m) операций, поэтому

$H\; f\; \in \; T\; I\; M\; E\; (f\; (m)\; 3).\; \{\backslash \; displaystyle\; H\_\; \{f\}\; \backslash \; in\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; (m)\; ^\; \{3\}\; \backslash \; right).\}$

Остальная часть доказательства покажет, что

$H\; f\; \notin \; TIME\; (е\; (\lfloor \; м\; 2\; \rfloor ))\; \{\backslash \; displaystyle\; H\_\; \{f\}\; \backslash \; notin\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; \backslash \; left\; (\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{m\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor)\; \backslash \; right)\; \backslash \; right)\}$

так что если мы подставим 2n + 1 вместо m, мы получим желаемый результат. Предположим, что H f находится в этом классе временной сложности, и мы попытаемся прийти к противоречию.

Если H f находится в этом классе временной сложности, это означает, что мы можем построить некоторую машину K, которая, учитывая некоторое описание машины [M] и ввод x, решает, будет ли кортеж ([M ], x) находится в H f в пределах

$TIME\; (f\; (\lfloor \; m\; 2\; \rfloor )).\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; \backslash \; left\; (\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{m\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right)\; \backslash \; right).\}$

Следовательно, мы можем используйте этот K для создания другой машины, N, которая принимает описание машины [M] и запускает K для кортежа ([M], [M]), а затем принимает, только если K отклоняет, и отклоняет, если K принимает. Если теперь n - длина входа в N, тогда m (длина входа в K) вдвое больше n плюс некоторый символ-разделитель, поэтому m = 2n + 1. Время работы N, таким образом, составляет

$TIME\; (f\; (\; \lfloor \; m\; 2\; \rfloor ))\; =\; ВРЕМЯ\; (f\; (\lfloor \; 2\; n\; +\; 1\; 2\; \rfloor ))\; =\; ВРЕМЯ\; (f\; (n)).\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; \backslash \; left\; (\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{m\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right)\; \backslash \; right)\; =\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; \backslash \; left\; (\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{2n\; +\; 1\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right)\; \backslash \; right)\; =\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; (n)\; \backslash \; right).\}$

Теперь, если мы введем [N] в качестве входных данных в саму N (что делает длину n равной [N]) и зададим вопрос, принимает ли N свое собственное описание в качестве входных данных, мы получим:

• Если N принимает [N] (что, как мы знаем, делает не более чем в f (n) операциях), это означает, что K отклоняет ([N], [N]), поэтому ([N ], [N]) не находится в H f, и, таким образом, N не принимает [N] в шагах f (n). Противоречие!
• Если N отклоняет [N] (что, как мы знаем, он делает не более чем в f (n) операциях), это означает, что K принимает ([N ], [N]), поэтому ([N], [N]) равно в H f, и, таким образом, N действительно принимает [N] в f (n) шаги. Противоречие!

Таким образом, мы заключаем, что машины K не существует, и поэтому

$H\; f\; \notin \; T\; I\; M\; E\; (f\; (\lfloor \; m\; 2\; \rfloor )).\; \{\backslash \; displaystyle\; H\_\; \{f\}\; \backslash \; notin\; \{\backslash \; mathsf\; \{TIME\}\}\; \backslash \; left\; (f\; \backslash \; left\; (\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{m\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right)\; \backslash \; right).\}$

Расширение

Читатель, возможно, понял, что доказательство проще, потому что мы выбрали простую симуляцию машины Тьюринга, для которой мы можем быть уверены, что

$H\; f\; \in \; TIME\; (f\; (m)\; 3).\; \{\backslash \; displaystyle\; H\_\; \{f\}\; \backslash \; in\; \{\backslash \; mathsf\; \{TIME\}\}\; (f\; (m)\; ^\; \{3\}).\}$

Было показано, что существует более эффективная модель моделирования, которая устанавливает, что

$H\; е\; \in \; ВРЕМЯ\; (е\; (м)\; журнал\; \; е\; (м))\; \{\backslash \; Displaystyle\; H\_\; \{f\}\; \backslash \; in\; \{\backslash \; mathsf\; \{TIME\}\}\; (f\; (m)\; \backslash \; log\; f\; (m))\}$

но поскольку это модель симуляции довольно сложна, она здесь не включена.

Если g (n) является конструируемой функцией времени, и f (n + 1) = o (g (n)), то существует проблема решения, которая не может быть решена за недетерминированное время f (n), но может быть решена за недетерминированное время g (n). Другими словами, класс сложности NTIME (f (n)) является строгим подмножеством NTIME (g (n)).

Теоремы о иерархии времени гарантируют, что детерминированные и недетерминированные версии экспоненциальной иерархии являются подлинными иерархиями: другими словами P ⊊ EXPTIME ⊊ 2-EXP ⊊... и NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊....

Например, $P\; ⊊\; EXPTIME\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{P\}\}\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{EXPTIME\}\}\}$с $P\; \subseteq \; DTIME\; (2\; n)\; ⊊\; DTIME\; (2\; 2\; n)\; \subseteq \; EXPTIME\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{\; P\}\}\; \backslash \; substeq\; \{\backslash \; mathsf\; \{DTIME\}\}\; (2\; ^\; \{n\})\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{DTIME\}\}\; (2\; ^\; \{2n\})\; \backslash \; substeq\; \{\backslash \; mathsf\; \{EXPTIME\}\}\}$. Действительно, $DTIME\; (2\; n)\; \subseteq \; DTIME\; (o\; (2\; 2\; n\; 2\; n))\; ⊊\; DTIME\; (2\; 2\; n)\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; left\; (2\; ^\; \{n\}\; \backslash \; right)\; \backslash \; substeq\; \{\backslash \; mathsf\; \{DTIME\}\}\; \backslash \; left\; (o\; \backslash \; left\; (\{\backslash \; frac\; \{2\; ^\; \{2n\}\}\; \{2n\}\}\; \backslash \; right)\; \backslash \; right)\; \backslash \; subsetneq\; \{\backslash \; mathsf\; \{DTIME\}\}\; (2\; ^\; \{2n\; \})\}$из теоремы об иерархии времени.

Теорема также гарантирует, что существуют проблемы в P, требующие решения сколь угодно больших показателей; другими словами, P не сворачивается в DTIME (n) для любого фиксированного k. Например, есть задачи, которые можно решить за n раз, но не за n раз. Это один из аргументов против тезиса Кобэма, соглашения о том, что P является практическим классом алгоритмов. Если бы такой коллапс действительно произошел, мы могли бы вывести, что P≠ PSPACE, поскольку это хорошо известная теорема, что DTIME (f (n)) строго содержится в DSPACE (f (n)).

Однако теоремы иерархии времени не предоставляют средств для связи детерминированной и недетерминированной сложности или сложности времени и пространства, поэтому они не проливают света на большие нерешенные вопросы теории вычислительной сложности : являются ли Pи NP, NPи PSPACE, PSPACE и EXPTIME, или EXPTIME и NEXPTIME равно или нет.

• Теорема пространственной иерархии

• Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN 0-534-94728-X.Страницы 310–313 раздела 9.1: Теоремы об иерархии.
• Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 ​​.Раздел 7.2: Теорема об иерархии, стр. 143–146.