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

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

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

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

${\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)})}$,

где DTIME ( f ( n )) обозначает класс сложности задач принятия решений , разрешимых за время O ( f ( n )). Левый класс включает в себя немного обозначений o, ссылаясь на множество задач принятия решений, разрешимых за асимптотически меньшее , чем f ( n ) время.

В частности, это показывает, что тогда и только тогда , когда , то мы имеем бесконечную временную иерархию. ${\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}$ ${\displaystyle a<b}$

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

${\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))}$.

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

Фон

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

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

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

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

Заявление

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

${\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).}$

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

Пример. Существуют задачи, решаемые за время n log ² n , но не за время n . Это следует из установки , поскольку n находится в ${\displaystyle f(n)=n\log n}$

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

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

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

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

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

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

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

Мы знаем, что можем определить принадлежность H _f с помощью детерминированной машины Тьюринга R , которая моделирует M для f ( x ) шагов, сначала вычисляя f (| x |), а затем записывая строку нулей этой длины, а затем используя эту строку нулей в качестве «часов» или «счетчика» для моделирования M максимум на столько же шагов. На каждом шаге моделирующая машина должна просматривать определение M , чтобы решить, каким будет следующее действие. Можно с уверенностью сказать, что это займет максимум f ( m ) ³ операций (поскольку известно, что моделирование машины временной сложности T ( n ) для может быть достигнуто за время на многоленточной машине, где | M | — длина кодирования M ), мы имеем, что: ${\displaystyle O(T(n)\cdot |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 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 ] в качестве входных данных в сам 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 ]) находится в Hf _, и, таким образом, N принимает [ N ] за f ( 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))}$.

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

Если 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}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}$ ${\displaystyle {\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 ^4999. Это один из аргументов против тезиса Кобэма , соглашения о том, что P является практическим классом алгоритмов. Если бы такой коллапс действительно произошел, мы могли бы вывести, что P ≠ PSPACE , поскольку общеизвестна теорема, что DTIME ( f ( n )) строго содержится в DSPACE ( f ( n )).

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

Более точные теоремы об иерархии

Разрыв приблизительно между нижней и верхней границей времени в теореме об иерархии можно проследить до эффективности устройства, использованного в доказательстве, а именно универсальной программы, которая поддерживает подсчет шагов. Это можно сделать более эффективно на определенных вычислительных моделях. Самые точные результаты, представленные ниже, были доказаны для: ${\displaystyle \log f(n)}$

• Машина с произвольным доступом с единичной стоимостью ^[8]
• Модель языка программирования , программы которой работают на двоичном дереве, доступ к которому всегда осуществляется через его корень. Эта модель, представленная Нилом Д. Джонсом ^[9], сильнее детерминированной машины Тьюринга, но слабее машины с произвольным доступом.

Для этих моделей теорема имеет следующий вид:

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

Таким образом, постоянное увеличение временного ограничения позволяет решать больше задач, в отличие от ситуации для машин Тьюринга (см. Теорема о линейном ускорении ). Более того, Бен-Амрам доказал ^[10] , что в приведенных выше моделях для f полиномиальной скорости роста (но более чем линейной) имеет место тот случай , когда для всех существует проблема принятия решения, которая не может быть решена за наихудшее детерминированное время f ( n ), но может быть решена за наихудшее время . ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )f(n)}$

Смотрите также

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

Ссылки

1. Hartmanis, J. ; Stearns, RE (1 мая 1965 г.). «О вычислительной сложности алгоритмов». Труды Американского математического общества . 117 . Американское математическое общество: 285–306. doi : 10.2307/1994208 . ISSN  0002-9947. JSTOR  1994208. MR  0170805.
2. Хенни, ФК; Стернс, Р. Э. (октябрь 1966 г.). «Двухленточное моделирование многоленточных машин Тьюринга». J. ACM . 13 (4). Нью-Йорк, Нью-Йорк, США: ACM: 533–546. doi : 10.1145/321356.321362 . ISSN  0004-5411. S2CID  2347143.
3. Кук, Стивен А. (1972). «Иерархия для недетерминированной временной сложности». Труды четвертого ежегодного симпозиума ACM по теории вычислений . STOC '72. Денвер, Колорадо, США: ACM. стр. 187–192. doi : 10.1145/800152.804913 .
4. Сейферас, Джоэл И.; Фишер, Майкл Дж .; Мейер, Альберт Р. (январь 1978 г.). «Разделение недетерминированных классов временной сложности». J. ACM . 25 (1). Нью-Йорк, штат Нью-Йорк, США: ACM: 146–167. doi : 10.1145/322047.322061 . ISSN  0004-5411. S2CID  13561149.
5. Жак, Станислав (октябрь 1983 г.). «Иерархия времени машины Тьюринга». Теоретическая информатика . 26 (3). Elsevier Science BV: 327–333. дои : 10.1016/0304-3975(83)90015-4 .
6. Фортнау, Л.; Сантханам, Р. (2004). «Иерархические теоремы для вероятностного полиномиального времени». 45-й ежегодный симпозиум IEEE по основам компьютерной науки . стр. 316. doi :10.1109/FOCS.2004.33. ISBN 0-7695-2228-9. S2CID  5555450.
7. Сипсер, Майкл (27 июня 2012 г.). Введение в теорию вычислений (3-е изд.). Обучение CENGAGE. ISBN 978-1-133-18779-0.
8. Садборо, Иван Х.; Зальцберг, А. (1976). «О семействах языков, определяемых машинами с ограниченным временем доступа». Журнал SIAM по вычислениям . 5 (2): 217–230. doi :10.1137/0205018.
9. Джонс, Нил Д. (1993). «Постоянные факторы имеют значение». 25-й симпозиум по теории вычислений : 602–611. doi :10.1145/167088.167244. S2CID  7527905.
10. Бен-Амрам, Амир М. (2003). «Более тесные иерархии времени с постоянным фактором». Information Processing Letters . 87 (1): 39–44. doi :10.1016/S0020-0190(03)00253-9.

Дальнейшее чтение

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