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

Как детерминированные, так и недетерминированные машины могут решать больше задач, если им предоставить больше места

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

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

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

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 не может быть определено ТМ с использованием ячеек. Предполагая, что L может быть определено некоторой ТМ M с использованием ячеек, и следуя теореме Иммермана–Селепченьи , также может быть определено ТМ (называемой ) с использованием ячеек. Здесь кроется противоречие, поэтому предположение должно быть ложным: ${\displaystyle o(f(n))}$ ${\displaystyle o(f(n))}$ ${\displaystyle {\overline {L}}}$ ${\displaystyle {\overline {M}}}$ ${\displaystyle o(f(n))}$

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

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

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

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

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

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

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

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

Предположим, что f является пространственно-конструируемым. SPACE является детерминированным.

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

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

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

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

Следствия

Следствие 1

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

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

Следствие 2

NL ⊊ PSPACE .

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

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

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

Следствие 3

PSPACE ⊊ EXPSPACE .

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

Следствие 4

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

Следствие 5

ПРОСТРАНСТВО( n ) ≠ PВРЕМЯ .

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

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

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

Ссылки

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

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