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

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

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

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

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

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

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

Фон

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

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

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

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

Заявление

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

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

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

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

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

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

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

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

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

Чтобы доказать это, мы сначала определим язык кодировок машин и их входов, которые заставляют их останавливаться в пределах f

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

Обратите внимание, что это временной класс. Это набор пар машин и входов для этих машин ( M , x ) для этих машин, так что машина M принимает в течение f (| x |) шагов.

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

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

${\ 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 n + 1 вместо m , мы получим желаемый результат. Предположим, что H _f принадлежит этому классу временной сложности, и мы придем к противоречию.

Если H _f принадлежит этому классу временной сложности, то существует машина K, которая, учитывая некоторое описание машины [ M ] и ввод x , решает, находится ли кортеж ([ M ], x ) в H _{f в} пределах

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

Мы используем этот K для построения другой машины, N , которая берет машинное описание [ M ] и запускает K на кортеже ([ M ], [ M ]), т.е. M моделируется в собственном коде с помощью K , а затем N принимает, если K отклоняет, и отклоняет, если K принимает. Если n - длина входа в N , то m (длина входа в K ) вдвое больше n плюс некоторый символ-разделитель, поэтому m = 2 n + 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 в Now, если мы введем [ N ] в качестве входных данных в саму N (что делает n длиной [ N ]) и зададим вопрос, принимает ли N свое собственное описание в качестве входных данных, мы получим:

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

• Если N отклоняет [ N ] (что, как мы знаем, делает не более чем за f ( n ) операций), это означает, что K принимает ([ N ], [ N ]), поэтому ([ N ], [ N ]) находится в H _е , и , таким образом , 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}).}$

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

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

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

Обратите внимание, однако, что аргумент, идентичный приведенному выше, подразумевает, что не содержится в if - функция, которая дает время, в течение которого можно смоделировать машину с временной сложностью на входе . ${\ displaystyle DTIME (r (f (2m + 1)))}$${\ displaystyle DTIME (f (m))}$${\ Displaystyle г (е (| M | + | х |))}$${\ displaystyle M}$${\ Displaystyle f (п)}$${\ displaystyle x}$

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

Если 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 ⊊ ....

Например, поскольку . Действительно, из теоремы об иерархии времени. ${\ 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})}$

Теорема также гарантирует, что существуют проблемы в P, требующие решения сколь угодно больших показателей; другими словами, P не коллапсирует до DTIME ( n ^k ) для любого фиксированного 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.