Теорема пространственной иерархии - Space hierarchy theorem

Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: это написано от первого лица, как лекция, а не статья энциклопедии Пожалуйста помоги улучшить эту статью если вы можете. (Декабрь 2019 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

${ Displaystyle { mathsf {ПРОБЕЛ}} влево (о (е (п)) вправо) subsetneq { mathsf {ПРОБЕЛ}} (е (п))}$,

где ПРОБЕЛ означает либо DSPACE или NSPACE, и о относится к маленький о обозначение.

утверждение

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

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

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

Цель здесь - определить язык, который можно решить в космосе.${ Displaystyle О (е (п))}$ но не космос ${ Displaystyle о (е (п))}$. Здесь мы определяем язык L:

${ displaystyle L = {~ ( langle M rangle, 10 ^ {k}): M { mbox {не принимает}} ( langle M rangle, 10 ^ {k}) { mbox {с использованием пробел}} leq f (| langle M rangle, 10 ^ {k} |) ~ }}$

Теперь для любой машины M что решает язык в космосе ${ Displaystyle о (е (п))}$, L будет отличаться хотя бы в одном месте от языка M. А именно, для некоторого достаточно большого k, M будет использовать пространство ${ Displaystyle Leq е (| langle M rangle, 10 ^ {k} |)}$ на ${ displaystyle ( langle M rangle, 10 ^ {k})}$ и поэтому будет отличаться по своей стоимости.

С другой стороны, L в ${ Displaystyle { mathsf {ПРОБЕЛ}} (е (п))}$. Алгоритм выбора языка L составляет:

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

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

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

В случае NPSPACE мы сначала переопределим L:

${ displaystyle L = {~ ( langle M rangle, 10 ^ {k}): M { mbox {принимает}} ( langle M rangle, 10 ^ {k}) { mbox {с использованием пробела} } leq f (| langle M rangle, 10 ^ {k} |) ~ }}$

Теперь нам нужно изменить алгоритм, чтобы он принимал L изменив шаг 4 на:

• Если M принято Икс во время этого моделирования, затем принять; в противном случае, отвергать.

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

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

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

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

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

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

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

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

Если пространство измеряется как количество используемых ячеек независимо от размера алфавита, тогда ${ Displaystyle { mathsf {ПРОБЕЛ}} (е (п)) = { mathsf {ПРОБЕЛ}} (О (е (п)))}$ потому что можно добиться любого линейного сжатия, переключившись на более крупный алфавит. Однако, измеряя пространство в битах, можно добиться более четкого разделения для детерминированного пространства. Вместо определения с точностью до мультипликативной константы, пространство теперь определяется с точностью до аддитивной константы. Однако, поскольку любое постоянное количество внешнего пространства можно сэкономить, сохранив содержимое во внутреннем состоянии, у нас все еще есть ${ Displaystyle { mathsf {ПРОБЕЛ}} (е (п)) = { mathsf {ПРОБЕЛ}} (е (п) + О (1))}$.

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

• Для широкого спектра последовательных вычислительных моделей, в том числе для машин Тьюринга, SPACE (ж(п)-ω (журнал(ж(п)+п))) ⊊ ПРОБЕЛ (ж(п)). Это верно, даже если ПРОБЕЛ (ж(п)-ω(журнал(ж(п)+п))) определяется с использованием другой вычислительной модели, чем ${ Displaystyle { mathsf {ПРОБЕЛ}} (е (п))}$ потому что разные модели могут имитировать друг друга с помощью ${ Displaystyle О ( журнал (е (п) + п))}$ пространство над головой.
• Для некоторых вычислительных моделей у нас даже есть ПРОБЕЛ (ж(п)-ω(1)) ⊊ ПРОБЕЛ (ж(п)). В частности, это справедливо для машин Тьюринга, если мы зафиксируем алфавит, количество головок на входной ленте, количество головок на рабочей ленте (используя одну рабочую ленту) и добавим разделители для посещенной части рабочей ленты (которые могут быть проверено без увеличения использования пространства). КОСМОС(ж(п)) не зависит от того, бесконечная или полубесконечная рабочая лента. У нас также может быть фиксированное количество рабочих лент, если ж(п) представляет собой либо конструктивный кортеж SPACE, определяющий использование пространства на ленте, либо SPACE (ж(п)-ω(журнал(ж(п))) - конструируемое число, дающее общее использование пространства (не считая накладных расходов на хранение длины каждой ленты).

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

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

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

Следствия

Следствие 1.

Для любых двух функций ${ displaystyle f_ {1}}$, ${ displaystyle f_ {2}: mathbb {N} longrightarrow mathbb {N}}$, где ${ displaystyle f_ {1} (п)}$ является ${ Displaystyle о (е_ {2} (п))}$ и ${ displaystyle f_ {2}}$ конструктивно в пространстве, ${ Displaystyle { mathsf {ПРОБЕЛ}} (е_ {1} (п)) subsetneq { mathsf {ПРОБЕЛ}} (е_ {2} (п))}$.

Это следствие позволяет нам разделить различные классы сложности пространства. ${ Displaystyle п ^ {к}}$ конструктивно в пространстве для любого натурального числа k. Поэтому для любых двух натуральных чисел ${ displaystyle k_ {1}$ мы можем доказать ${ Displaystyle { mathsf {ПРОБЕЛ}} (п ^ {к_ {1}}) subsetneq { mathsf {ПРОБЕЛ}} (п ^ {к_ {2}})}$. Мы можем распространить эту идею на действительные числа в следующем следствии. Это демонстрирует подробную иерархию внутри класса PSPACE.

Следствие 2.

Для любых двух неотрицательных действительных чисел ${ displaystyle a_ {1}$.

Следствие 3.

NL ⊊ PSPACE.

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

Теорема савича показывает, что ${ Displaystyle { mathsf {NL}} substeq { mathsf {ПРОБЕЛ}} ( log ^ {2} n)}$, а теорема пространственной иерархии показывает, что ${ Displaystyle { mathsf {ПРОБЕЛ}} ( log ^ {2} п) subsetneq { mathsf {ПРОБЕЛ}} (п)}$. Таким образом, мы получаем это следствие вместе с тем фактом, что TQBF ∉ NL, поскольку TQBF является PSPACE-полным.

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

Следствие 4.

PSPACE ⊊ EXPSPACE.

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

Следствие 5.

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

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

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

использованная литература

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