ДСПЕЙС

Информацию о цифровых репозиториях см. в DSpace .

В сложности вычислений теории DSPACE или SPACE — это вычислительный ресурс, описывающий ресурс пространства памяти для детерминированной машины Тьюринга . Он представляет собой общий объем памяти, который понадобится «нормальному» физическому компьютеру для решения данной вычислительной задачи с помощью данного алгоритма .

Классы сложности

Мера DSPACE используется для определения классов сложности , наборов всех задач решения , которые можно решить, используя определенный объем памяти. Для каждой функции f ( n ) существует класс сложности SPACE( f ( n )), набор задач решения , которые могут быть решены детерминированной машиной Тьюринга с использованием пространства O ( f ( n )). Нет ограничений на количество времени вычислений используемого , хотя могут быть ограничения на некоторые другие меры сложности (например, чередование ).

Несколько важных классов сложности определены в терминах DSPACE . К ним относятся:

• REG = DSPACE( O (1)), где REG — класс регулярных языков . Фактически, REG = DSPACE( o (log log n )) (т. е Ω(log log n ) . . для распознавания любого нерегулярного языка требуется пространство

Доказательство: Предположим, что существует нерегулярный язык L ∈ DSPACE( s ( n )), для s ( n ) = o (log log n ). Пусть M — машина Тьюринга , решающая L в пространстве s ( n ). По нашему предположению L ∉ DSPACE( O (1)); таким образом, для любого произвольного $k\in \mathbb {N}$, существует вход M , требующий больше места, чем k .

Пусть x — вход наименьшего размера, обозначаемый n, который требует больше места, чем k , и ${\mathcal {C}}$ набором всех конфигураций M . на входе x быть Поскольку M ∈ DSPACE( s ( n )), то $|{\mathcal {C}}|\leq 2^{c.s(n)}=o(\log n)$, где c — константа, зависящая M. от

Обозначим через множество всех возможных последовательностей пересечений M S на x . Заметим, что длина последовательности пересечений M по x не превосходит $|{\mathcal {C}}|$: если оно длиннее, то какая-то конфигурация повторится, и M перейдет в бесконечный цикл. Есть также максимум $|{\mathcal {C}}|$ возможностей для каждого элемента пересекающейся последовательности, поэтому количество различных пересекающихся последовательностей M по x равно

$|S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c.s(n)})^{2^{c.s(n)}}=2^{c.s(n).2^{c.s(n)}}<2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}}=o(n)$

Согласно принципу «ячейки» , существуют индексы i < j такие, что ${\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)$, где ${\mathcal {C}}_{i}(x)$ и ${\mathcal {C}}_{j}(x)$ — это пересекающиеся последовательности на границе i и j соответственно.

Пусть x' будет строкой, полученной из x путем удаления всех ячеек от i + 1 до j . Машина M точно так же, по-прежнему ведет себя на входе x' как и на входе x ей требуется то же самое пространство, , поэтому для вычисления x' что и для вычисления x . Однако | х' | < | х | , что противоречит определению x . Следовательно, не существует такого языка L, как предполагалось. □

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

• L = DSPACE( O (log n ))
• PSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})$
• EXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})$

Модели машин

DSPACE традиционно измеряется на детерминированной машине Тьюринга . Несколько важных классов пространственной сложности являются сублинейными , то есть меньше размера входных данных. Таким образом, «взимание платы» с алгоритма за размер входных данных или за размер выходных данных не будет по-настоящему захватывать используемое пространство памяти. Это решается путем определения многоленточной машины Тьюринга с входом и выходом , которая является стандартной многоленточной машиной Тьюринга, за исключением того, что на входную ленту никогда нельзя записывать, а выходную ленту нельзя читать. Это позволяет определять меньшие классы пространства, такие как L (логарифмическое пространство), исходя из объема пространства, используемого всеми рабочими лентами (за исключением специальных входных и выходных лент).

Поскольку многие символы можно упаковать в один, взяв подходящую степень алфавита, для всех c ≥ 1 и f таких, что f ( n ) ≥ 1 , класс языков, распознаваемых в пространстве cf ( n ), тот же, что и класс языков, распознаваемых в пространстве f ( n ). Это оправдывает использование большой буквы О в определении.

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

Теорема о пространственной иерархии показывает, что для любой конструируемой в пространстве функции $f:\mathbb {N} \to \mathbb {N}$, существует некоторый язык L, разрешимый в пространстве $O(f(n))$ но не в космосе $o(f(n))$.

Дополнительная информация: теорема о пространственной иерархии.

Связь с другими классами сложности

DSPACE — детерминированный аналог NSPACE , класса пространства памяти на недетерминированной машине Тьюринга . По Савича теореме у нас есть это

${\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].$

NTIME связан с DSPACE следующим образом. Для любой конструктивной по времени функции t ( n ) мы имеем

${\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))$.

Ссылки

• Шепетовский, Анджей (1994). Машины Тьюринга с сублогарифмическим пространством . Springer Science+Business Media . ISBN  978-3-540-58355-4 .
• Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN  978-0-521-42426-4 . Збл   1193.68112 .

Внешние ссылки

• Зоопарк сложности : DSPACE( f ( n )) .