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

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

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

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

.

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

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

.

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

Фон [ править ]

Обе теоремы используют понятие функции, построенной по времени . Функция занимает много времени конструктивно , если существует детерминированный машин Тьюринга такого , что для каждого , если машина запускается с входом п единиц, это будет после того, как остановить именно е ( п ) шагов. Все полиномы с неотрицательными целыми коэффициентами могут быть построены по времени, как и экспоненциальные функции, такие как 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 ) ² .

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

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

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

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

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

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

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 в} пределах

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

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

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

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

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

Расширение [ править ]

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

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

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

H_{f}\in {\mathsf {TIME}}(f(m)\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 ⊊ ....

Например, поскольку . Действительно, из теоремы об иерархии времени. ${\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}$ ${\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}$ ${\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\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 равны или нет.

См. Также [ править ]

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

Ссылки [ править ]

^ Хартманис, Дж . ; Стернс, RE (1 мая 1965 г.). «О вычислительной сложности алгоритмов» . Труды Американского математического общества . Американское математическое общество. 117 : 285–306. DOI : 10.2307 / 1994208 . ISSN 0002-9947 . JSTOR 1994 208 . Руководство по ремонту 0170805 .
^ Хенни, ФК; Stearns, RE (октябрь 1966 г.). «Двухленточное моделирование многоленточных машин Тьюринга». J. ACM . Нью-Йорк, Нью-Йорк, США: ACM. 13 (4): 533–546. DOI : 10.1145 / 321356.321362 . ISSN 0004-5411 .
^ Кук, Стивен А. (1972). «Иерархия для недетерминированной временной сложности». Материалы четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '72. Денвер, Колорадо, США: ACM. С. 187–192. DOI : 10.1145 / 800152.804913 .
^ Seiferas, Иоиль I .; Фишер, Майкл Дж .; Мейер, Альберт Р. (январь 1978 г.). «Разделение недетерминированных классов временной сложности». J. ACM . Нью-Йорк, Нью-Йорк, США: ACM. 25 (1): 146–167. DOI : 10.1145 / 322047.322061 . ISSN 0004-5411 .
^ Ák, Станислав (октябрь 1983 г.). «Иерархия времени машины Тьюринга». Теоретическая информатика . Elsevier Science BV 26 (3): 327–333. DOI : 10.1016 / 0304-3975 (83) 90015-4 .
^ Fortnow, L .; Сантханам, Р. (2004). "Теоремы об иерархии для вероятностного полиномиального времени". 45-й ежегодный симпозиум IEEE по основам информатики . п. 316. DOI : 10.1109 / FOCS.2004.33 . ISBN 0-7695-2228-9.
^ Лука Тревизан, Заметки о теоремах иерархии , Калифорнийский университет в Беркли

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

[1] Хартманис, Дж . ; Стернс, RE (1 мая 1965 г.). «О вычислительной сложности алгоритмов» . Труды Американского математического общества . Американское математическое общество. 117 : 285–306. DOI : 10.2307 / 1994208 . ISSN 0002-9947 . JSTOR 1994 208 . Руководство по ремонту 0170805 .

[2] Хенни, ФК; Stearns, RE (октябрь 1966 г.). «Двухленточное моделирование многоленточных машин Тьюринга». J. ACM . Нью-Йорк, Нью-Йорк, США: ACM. 13 (4): 533–546. DOI : 10.1145 / 321356.321362 . ISSN 0004-5411 .

[3] Кук, Стивен А. (1972). «Иерархия для недетерминированной временной сложности». Материалы четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '72. Денвер, Колорадо, США: ACM. С. 187–192. DOI : 10.1145 / 800152.804913 .

[4] Seiferas, Иоиль I .; Фишер, Майкл Дж .; Мейер, Альберт Р. (январь 1978 г.). «Разделение недетерминированных классов временной сложности». J. ACM . Нью-Йорк, Нью-Йорк, США: ACM. 25 (1): 146–167. DOI : 10.1145 / 322047.322061 . ISSN 0004-5411 .

[5] Ák, Станислав (октябрь 1983 г.). «Иерархия времени машины Тьюринга». Теоретическая информатика . Elsevier Science BV 26 (3): 327–333. DOI : 10.1016 / 0304-3975 (83) 90015-4 .

[6] Fortnow, L .; Сантханам, Р. (2004). "Теоремы об иерархии для вероятностного полиномиального времени". 45-й ежегодный симпозиум IEEE по основам информатики . п. 316. DOI : 10.1109 / FOCS.2004.33 . ISBN 0-7695-2228-9.

[7] Лука Тревизан, Заметки о теоремах иерархии , Калифорнийский университет в Беркли

[1]