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

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

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

Теоремы о пространственной иерархии основаны на концепции пространственно-конструируемых функций . Теоремы о детерминированной и недетерминированной пространственной иерархии утверждают, что для всех конструируемых в пространстве функций f ( n )

{\mathsf {SPACE}}\left(o(f(n))\right)\subsetneq {\mathsf {SPACE}}(f(n))

,

где SPACE означает DSPACE или NSPACE , а $o$ относится к маленькому обозначению o .

Заявление

Формально функция $f:\mathbb {N} \longrightarrow \mathbb {N}$ является пространственно-конструируемым, если $f(n)\geq \log ~n$ и существует машина Тьюринга который вычисляет функцию $f(n)$ в космосе $O(f(n))$ при запуске с входом $1^{n}$ , где $1^{n}$ представляет строку из n последовательных единиц. Большинство общих функций, с которыми мы работаем, являются конструируемыми в пространстве, включая полиномы, показатели степени и логарифмы.

Для каждой пространственно-конструируемой функции $f:\mathbb {N} \longrightarrow \mathbb {N}$ , существует язык $L$ , разрешимый в пространстве $O(f(n))$ но не в космосе $o(f(n))$ .

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

Цель состоит в том, чтобы определить язык, который можно будет решать в пространстве. $O(f(n))$ но не космос $o(f(n))$ . Язык определяется как $L$ :

$L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and time }}\leq 2^{f(|\langle M\rangle ,10^{k}|)}{\mbox{ and }}M{\mbox{ does not accept }}(\langle M\rangle ,10^{k})~\}$

Для любой машины $M$ , которая определяет язык в пространстве $o(f(n))$ , $L$ будет отличаться хотя бы в одном месте от языка $M$ . А именно, для некоторого достаточно большого $M$ k $будет$ использовать пространство $\leq f(|\langle M\rangle ,10^{k}|)$ на $(\langle M\rangle ,10^{k})$ и, следовательно, будет отличаться по своей стоимости.

С другой стороны, $L$ находится в ${\mathsf {SPACE}}(f(n))$ . Алгоритм выбора языка $L$ следующий:

На входе $x$ вычислите $f(|x|)$ используя пространственную конструкцию, и отметьте $f(|x|)$ ячейки ленты. Всякий раз, когда предпринимается попытка использовать более $f(|x|)$ клетки, отвергают .
Если $x$ не имеет вида $\langle M\rangle ,10^{k}$ для некоторых $M$ TM отклонить .
Имитировать $M$ на входе $x$ не более $2^{f(|x|)}$ шаги (с помощью $f(|x|)$ космос). Если симуляция пытается использовать более $f(|x|)$ пространство или более $2^{f(|x|)}$ операции, затем отклоните .
Если $M$ принял $x$ во время этой симуляции, то отклоните ; в противном случае примите .

Примечание к шагу 3: Выполнение ограничено $2^{f(|x|)}$ шаги, чтобы избежать случая, когда $M$ не останавливается на входе $x$ . То есть случай, когда $M$ занимает пространство всего $O(f(x))$ как требуется, но работает бесконечное время.

Приведенное выше доказательство справедливо для случая PSPACE, но для случая NPSPACE необходимо внести некоторые изменения. Важным моментом является то, что, хотя в детерминированной TM принятие и отклонение могут быть инвертированы (важно для шага 4), на недетерминированной машине это невозможно.

В случае NPSPACE $L$ сначала необходимо переопределить :

$L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and }}M{\mbox{ accepts }}(\langle M\rangle ,10^{k})~\}$

Теперь алгоритм необходимо изменить, чтобы принять $L$ , изменив шаг 4 следующим образом:

Если $M$ принял $x$ во время этой симуляции, тогда примите ; в противном случае отклонить .

$L$ не может быть определено ТМ с использованием $o(f(n))$ клетки. Предполагая, что $L$ может быть решено некоторым TM $M,$ используя $o(f(n))$ ячеек и, как следует из теоремы Иммермана–Селепшени , ${\overline {L}}$ также может быть определено с помощью TM (так называемого ${\overline {M}}$ ) с использованием $o(f(n))$ клетки. Здесь кроется противоречие, следовательно, предположение должно быть ложным:

Если $w=(\langle {\overline {M}}\rangle ,10^{k})$ (для некоторого достаточно большого $k$ ) не входит в ${\overline {L}}$ тогда $M$ примет это, следовательно ${\overline {M}}$ отвергает $w$ , поэтому $w$ находится в ${\overline {L}}$ (противоречие).
Если $w=(\langle {\overline {M}}\rangle ,10^{k})$ (для некоторого достаточно большого $k$ ) находится в ${\overline {L}}$ то $М$ отвергнет его, следовательно ${\overline {M}}$ принимает $w$ , поэтому $w$ нет в ${\overline {L}}$ (противоречие).

Сравнение и улучшения

Теорема о пространственной иерархии сильнее аналогичных теорем об иерархии времени по нескольким причинам:

Требуется только, чтобы s(n) было не менее log n, а не не менее n .
Он может разделять классы с любой асимптотической разницей, тогда как теорема об иерархии времени требует, чтобы они были разделены логарифмическим коэффициентом.
Для этого требуется только, чтобы функция была конструируемой в пространстве, а не во времени.

Кажется, легче разделить классы в пространстве, чем во времени. Действительно, в то время как теорема об иерархии времени не претерпела значительных улучшений с момента ее создания, теорема о недетерминированной пространственной иерархии претерпела по крайней мере одно важное улучшение, сделанное Вильямом Геффертом в его статье 2003 года «Пересмотренная теорема о пространственной иерархии». В этой статье сделано несколько обобщений теоремы:

Это ослабляет требования к пространственной конструкции. Вместо простого разделения классов-объединений ⁠ ${\mathsf {DSPACE}}(O(s(n))$ ⁠ и ⁠ ${\mathsf {DSPACE}}(o(s(n))$ ⁠ , оно отделяется ⁠ ${\mathsf {DSPACE}}(f(n))$ ⁠ из ⁠ ${\mathsf {DSPACE}}(g(n))$ ⁠ где ⁠ $f(n)$ ⁠ — произвольный ⁠ $O(s(n))$ ⁠ функция и g(n) — вычислимая ⁠ $o(s(n))$ ⁠ функция. Эти функции не обязательно должны быть конструируемыми в пространстве или даже монотонно возрастающими.
Он идентифицирует унарный язык или язык счета, который принадлежит к одному классу, но не относится к другому. В исходной теореме язык разделения был произвольным.
Это не требует ⁠ $s(n)$ ⁠ быть не ниже log n ; это может быть любая недетерминированная, полностью конструируемая в пространстве функция.

Уточнение пространственной иерархии

Если пространство измеряется количеством используемых ячеек независимо от размера алфавита, то ⁠ ${\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(O(f(n)))$ ⁠ потому что можно добиться любого линейного сжатия, перейдя на более крупный алфавит. Однако, измеряя пространство в битах, можно добиться гораздо более четкого разделения детерминированного пространства. Вместо определения с точностью до мультипликативной константы пространство теперь определяется с точностью до аддитивной константы. Однако, поскольку любой постоянный объем внешнего пространства можно сохранить, сохранив содержимое во внутреннем состоянии, у нас все еще есть ⁠ ${\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(f(n)+O(1))$ ⁠ .

Предположим, что f конструируемо в пространстве. ПРОСТРАНСТВО детерминировано.

Для широкого спектра последовательных вычислительных моделей, в том числе для машин Тьюринга, SPACE( f ( n ) - ω (log ( f ( n ) + n ))) ⊊ SPACE ( f ( n )). Это справедливо, даже если SPACE( f ( n ) - ω (log( f ( n ) + n ))) определяется с использованием другой вычислительной модели, чем ⁠ ${\mathsf {SPACE}}(f(n))$ ⁠ потому что разные модели могут имитировать друг друга с помощью ⁠ $O(\log(f(n)+n))$ ⁠ пространство над головой.
Для некоторых вычислительных моделей мы даже имеем SPACE( f ( n ) - ω (1)) ⊊ SPACE ( f ( n )). В частности, это справедливо для машин Тьюринга, если мы зафиксируем алфавит, количество головок на входной ленте, количество головок на рабочей ленте (используя одну рабочую ленту) и добавим разделители для посещенной части рабочей ленты (которые могут проверяться без увеличения использования пространства). SPACE( f ( n )) не зависит от того, является ли рабочая лента бесконечной или полубесконечной. Мы также можем иметь фиксированное количество рабочих лент, если f ( n ) является либо конструируемым кортежем SPACE, указывающим использование пространства на ленту, либо SPACE( f ( n )- ω (log( f ( n )))-конструируемым числом давая общее использование пространства (не считая накладных расходов на хранение длины каждой ленты).

Доказательство аналогично доказательству теоремы о пространственной иерархии, но с двумя сложностями: универсальная машина Тьюринга должна быть экономичной, а обращение должно быть экономичным. Обычно можно построить универсальные машины Тьюринга с помощью ⁠ $O(\log(space))$ ⁠ накладные расходы, а при соответствующих допущениях всего лишь ⁠ $O(1)$ ⁠ объем пространства (который может зависеть от моделируемой машины). Что касается разворота, ключевой вопрос заключается в том, как определить, отказывает ли моделируемая машина, входя в бесконечный (ограниченный по пространству) цикл. Простой подсчет количества сделанных шагов увеличит потребление пространства примерно на ⁠. $f(n)$ ⁠ . Ценой потенциально экспоненциального увеличения времени петли можно обнаружить с экономией пространства следующим образом: ^{[ 1 ]}

Измените машину, чтобы стереть все и в случае успеха перейти к определенной конфигурации A. Используйте поиск в глубину, чтобы определить, достижим ли A в пространстве, ограниченном начальной конфигурацией. Поиск начинается с A и проходит по конфигурациям, ведущим к A. Благодаря детерминизму это можно сделать на месте, не зацикливаясь.

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

Следствия

Следствие 1

Для любых двух функций $f_{1}$ , $f_{2}:\mathbb {N} \longrightarrow \mathbb {N}$ , где $f_{1}(n)$ является $o(f_{2}(n))$ и $f_{2}$ является пространственно-конструируемым, ${\mathsf {SPACE}}(f_{1}(n))\subsetneq {\mathsf {SPACE}}(f_{2}(n))$ .

Это следствие позволяет нам разделить различные классы пространственной сложности. Для любого натурального числа k функция $n^{k}$ является пространственно-конструируемым. Следовательно, для любых двух натуральных чисел $k_{1}<k_{2}$ мы можем доказывать ${\mathsf {SPACE}}(n^{k_{1}})\subsetneq {\mathsf {SPACE}}(n^{k_{2}})$ .

Следствие 2

НЛ ⊊ PSPACE .

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

Теорема Савича показывает, что ${\mathsf {NL}}\subseteq {\mathsf {SPACE}}(\log ^{2}n)$ , а теорема пространственной иерархии показывает, что ${\mathsf {SPACE}}(\log ^{2}n)\subsetneq {\mathsf {SPACE}}(n)$ . Результатом является это следствие, а также тот факт, что TQBF ∉ NL поскольку TQBF является PSPACE-полным.

Это также можно доказать, используя теорему о недетерминированной пространственной иерархии, чтобы показать, что NL ⊊ NPSPACE, и используя теорему Савича, чтобы показать, что PSPACE = NPSPACE.

Следствие 3

PSPACE ⊊ EXPSPACE .

Это последнее следствие показывает существование разрешимых проблем, которые являются неразрешимыми. Другими словами, их процедуры принятия решений должны использовать не только полиномиальное пространство.

Следствие 4

есть проблемы, В PSPACE для решения которых требуется сколь угодно большой показатель степени; поэтому PSPACE не сворачивается в DSPACE ( n ^к) для некоторой постоянной k .

Следствие 5

ПРОБЕЛ( n ) ≠ PTIME .

Чтобы увидеть это, предположим обратное, так любая проблема решается в космосе. $O(n)$ решается во времени $O(n^{c})$ и любая проблема $L$ решил в космосе $O(n^{b})$ решается во времени $O((n^{b})^{c})=O(n^{bc})$ . Сейчас ${\mathsf {P}}:=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})$ , таким образом, P замкнуто относительно такой замены границы, т.е. $\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{bk})\subseteq {\mathsf {P}}$ , так $L\in {\mathsf {P}}$ . Это означает, что для всех $b,{\mathsf {SPACE}}(n^{b})\subseteq {\mathsf {P}}\subseteq {\mathsf {SPACE}}(n)$ , но из теоремы о пространственной иерархии следует, что ${\mathsf {SPACE}}(n^{2})\not \subseteq {\mathsf {SPACE}}(n)$ , и отсюда следует следствие 6. Обратите внимание, что этот аргумент не доказывает, что ${\mathsf {P}}\not \subseteq {\mathsf {SPACE}}(n)$ ни это ${\mathsf {SPACE}}(n)\not \subseteq {\mathsf {P}}$ , поскольку для достижения противоречия мы использовали отрицание обоих предложений, то есть мы использовали оба включения, и можем только сделать вывод, что хотя бы одно неверно. В настоящее время неизвестно, какие из них терпят неудачу, но предполагается, что оба они терпят неудачу, то есть ${\mathsf {SPACE}}(n)$ и ${\mathsf {P}}$ несравнимы - по крайней мере, для детерминированного пространства. ^{[ 2 ]} Этот вопрос связан с вопросом о временной сложности (недетерминированных) линейных ограниченных автоматов, допускающих класс сложности ${\mathsf {NSPACE}}(n)$ (также известные как контекстно-зависимые языки , CSL); таким образом, согласно вышеизложенному, CSL не является разрешимой за полиномиальное время - см. также две проблемы Куроды о LBA .

См. также

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

Ссылки

^ Сипсер, Майкл (1978). «Остановка пространственных вычислений». Материалы 19-го ежегодного симпозиума по основам информатики .
^ «Откуда мы знаем, что P != LINSPACE, не зная, является ли одно подмножеством другого?» .

Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN 978-0-521-42426-4 . Збл 1193.68112 .
Лука Тревизан . Замечания по теоремам об иерархии . Раздаточный материал 7. CS172: Автоматы, вычислимость и сложность. Калифорнийский университет в Беркли. 26 апреля 2004 г.
Вильям Гефферт . Пересмотренная теорема о пространственной иерархии . Теоретическая информатика , том 295, номер 1–3, с. 171-187. 24 февраля 2003 г.
Сипсер, Майкл (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 0-534-94728-Х . Страницы 306–310 раздела 9.1: Теоремы об иерархии.
Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 . Раздел 7.2: Теорема об иерархии, стр. 143–146.

[1] Сипсер, Майкл (1978). «Остановка пространственных вычислений». Материалы 19-го ежегодного симпозиума по основам информатики .

[2] «Откуда мы знаем, что P != LINSPACE, не зная, является ли одно подмножеством другого?» .

[ 1 ]

[ 2 ]