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

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

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

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

,

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

Заявление

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

Для каждой пространственно-конструктивной функции существует язык L, который разрешим в пространстве, но не в пространстве .

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

Цель здесь - определить язык, который можно решать в пространстве, но не в пространстве . Здесь мы определяем язык L :

Теперь для любой машины M , которая решает язык в пространстве , L будет отличаться по крайней мере , одно место от языка М . А именно, для некоторого достаточно большого k , M будет использовать пространство на и, следовательно, будет отличаться по своему значению.

С другой стороны, L находится внутри . Алгоритм выбора языка L следующий:

  1. На входе x вычислите, используя конструктивность пространства, и отметьте ячейки ленты. Всякий раз , когда делается попытка использовать более клеток, отвергают .
  2. Если x не имеет формы для некоторого TM M , отклоните .
  3. Смоделируйте M на входе x не более чем для шагов (используя пробел). Если моделирование пытается использовать больше места или больше операций, то отклоните .
  4. Если M принял x во время этой симуляции, то отклонить ; в противном случае примите .

Примечание к шагу 3: выполнение ограничено шагами, чтобы избежать случая, когда M не останавливается на входе x . То есть случай, когда M потребляет пространство только по мере необходимости, но работает в течение бесконечного времени.

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

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

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

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

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

  1. Если (для некоторого достаточно большого k ) не находится в, то M примет его, поэтому отклоняет w , следовательно, w находится в (противоречие).
  2. Если (для некоторого достаточно большого k ) находится в, то M отклонит его, поэтому принимает w , следовательно, w не входит (противоречие).

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

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

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

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

  • Это снижает требования к простоте конструкции. Вместо того, чтобы просто разделять классы объединения и , он отделяется от где - произвольная функция, а g (n) - вычислимая функция. Эти функции не обязательно должны быть пространственно-конструктивными или даже монотонно возрастающими.
  • Он определяет унарный язык , или язык подсчета, который принадлежит одному классу, но не принадлежит другому. В исходной теореме разделяющий язык был произвольным.
  • Необязательно, чтобы было хотя бы log n ; это может быть любая недетерминированная полностью пространственно-конструктивная функция.

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

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

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

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

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

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

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

Следствия

Следствие 1.

Для любых двух функций , где есть и пространство-конструктивно, .

Это следствие позволяет разделить различные классы сложности пространства. Ведь любая функция конструктивна в пространстве для любого натурального числа k. Поэтому для любых двух натуральных чисел мы можем доказать . Мы можем распространить эту идею на действительные числа в следующем следствии. Это демонстрирует подробную иерархию внутри класса PSPACE.

Следствие 2.

Для любых двух неотрицательных действительных чисел .

Следствие 3.

NLPSPACE .

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

Теорема Савича показывает это , тогда как теорема пространственной иерархии показывает это . Таким образом, мы получаем это следствие вместе с тем фактом, что TQBF ∉ NL, поскольку TQBF является PSPACE-полным.

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

Следствие 4.

PSPACEEXPSPACE .

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

Следствие 5.

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

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

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