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

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

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

{\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 ) время.

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

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

{\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))

.

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

Предыстория [ править ]

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

Обзор доказательств [ править ]

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

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

Заявление [ править ]

Теорема об иерархии времени. Если f ( n ) является конструируемой по времени функцией, то существует проблема принятия решения , которую нельзя решить за детерминированное время в худшем случае o ( f ( n )) но можно решить за детерминированное время в худшем случае O ( f ( n ) )log f ( n )). Таким образом
${\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).$

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

Пример. Есть проблемы, решаемые за время n log ²n, но не время n . Это следует за установкой $f(n)=n\log n$ , поскольку n находится в

o\left(n\log n\right).

Доказательство [ править ]

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

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

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 ) for может быть достигнуто за время $O(T(n)\cdot |M|)$ на многоленточной машине, где | М | — длина кодировки 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 ]), т.е. M моделируется с помощью собственного кода с помощью K , а затем N принимает, если 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 ]) за 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 _f , и, таким образом, N принимает [ N ] за f ( 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 . Например, существуют задачи, решаемые в n ⁵⁰⁰⁰ время, но не н ⁴⁹⁹⁹ время. Это один из аргументов против тезиса Кобэма о том, что P является практическим классом алгоритмов. Если бы такой коллапс действительно произошел, мы могли бы сделать вывод, что P ≠ PSPACE , поскольку хорошо известна теорема о том, что DTIME ( f ( n )) строго содержится в DSPACE ( f ( n )).

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

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

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

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

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

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

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

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

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

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

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

Дальнейшее чтение [ править ]

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

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

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

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

[4] Сейферас, Джоэл И.; Фишер, Майкл Дж .; Мейер, Альберт Р. (январь 1978 г.). «Разделение недетерминированных классов временной сложности» . Дж. АКМ . 25 (1). Нью-Йорк, штат Нью-Йорк, США: ACM: 146–167. дои : 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. дои : 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 Journal по вычислительной технике . 5 (2): 217–230. дои : 10.1137/0205018 .

[9] Джонс, Нил Д. (1993). «Постоянные факторы имеют значение». 25-й симпозиум по теории вычислений : 602–611. дои : 10.1145/167088.167244 . S2CID 7527905 .

[10] Бен-Амрам, Амир М. (2003). «Более жесткие временные иерархии с постоянным коэффициентом». Письма об обработке информации . 87 (1): 39–44. дои : 10.1016/S0020-0190(03)00253-9 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]