Теорема об иерархии времени - Time hierarchy theorem

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

Теорема об иерархии времени для детерминированные многоленточные машины Тьюринга был впервые доказан Ричард Э. Стернс и Юрис Хартманис в 1965 г.^[1] Год спустя он был улучшен, когда Ф. К. Хенни и Ричард Э. Стернс повысили эффективность Универсальная машина Тьюринга.^[2] Следуя теореме, для любого детерминированного ограниченного по времени класс сложности, существует строго больший ограниченный по времени класс сложности, поэтому ограниченная по времени иерархия классов сложности не разрушается полностью. Точнее, теорема об иерархии времени для детерминированных машин Тьюринга утверждает, что для всех временные функции ж(п),

${ Displaystyle { mathsf {DTIME}} left (о left ({ frac {f (n)} { log f (n)}} right) right) subsetneq { mathsf {DTIME}} (f (n))}$.

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

${ Displaystyle { mathsf {NTIME}} (е (п)) subsetneq { mathsf {NTIME}} (г (п))}$.

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

Фон

Обе теоремы используют понятие временная функция. А функция ${ displaystyle f: mathbb {N} rightarrow mathbb {N}}$ конструктивно во времени, если существует детерминированная Машина Тьюринга так что для каждого ${ Displaystyle п в mathbb {N}}$, если машина запускается с вводом п один, он остановится ровно через ж(п) шаги. Все многочлены с неотрицательными целыми коэффициентами могут быть построены по времени, как и экспоненциальные функции, такие как 2^п.

Обзор доказательств

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

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

утверждение

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

${ displaystyle { mathsf {DTIME}} (f (n)) subsetneq { mathsf {DTIME}} left (f (n) ^ {2} right).}$

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

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

${ Displaystyle { mathsf {DTIME}} left (о left ({ frac {f (n)} { log f (n)}} right) right) subsetneq { mathsf {DTIME}} left (f (n) right).}$

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

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

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

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

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

${ displaystyle H_ {f} = left {([M], x) | M { text {accept}} x { text {in}} f (| x |) { text {steps}} right }.}$

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

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

${ displaystyle H_ {f} in { mathsf {TIME}} left (f (m) ^ {3} right).}$

Дальнейшее доказательство покажет, что

${ displaystyle H_ {f} notin { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right)}$

так что если мы подставим 2п +1 для м, получаем желаемый результат. Предположим, что ЧАС_ж находится в этом классе временной сложности, и мы попытаемся прийти к противоречию.

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

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

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

${ displaystyle { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right) = { mathsf {TIME}} left (f left ( left lfloor { frac {2n + 1} {2}} right rfloor right) right) = { mathsf {TIME}} left (f (n) right) .}$

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

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

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

${ displaystyle H_ {f} notin { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right).}$

Расширение

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

${ displaystyle H_ {f} in { mathsf {TIME}} (f (m) ^ {3}).}$

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

${ displaystyle H_ {f} in { mathsf {TIME}} (f (m) log f (m))}$

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

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

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

Последствия

Теоремы о временной иерархии гарантируют, что детерминированные и недетерминированные версии экспоненциальная иерархия настоящие иерархии: другими словами п ⊊ EXPTIME ⊊ 2-ЕХР ⊊ ... и НП ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....

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

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

Однако теоремы о иерархии времени не предоставляют средств для связи детерминированной и недетерминированной сложности или сложности времени и пространства, поэтому они не проливают света на большие нерешенные вопросы теория сложности вычислений: ли п и НП, НП и 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.