DSPACE

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  "DSPACE"  -  новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Классы сложности [ править ]

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

В терминах DSPACE определены несколько важных классов сложности . Они включают:

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

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

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

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

${\displaystyle |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 , что , где и - последовательности пересечения на границе i и j , соответственно.${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$${\displaystyle {\mathcal {C}}_{i}(x)}$${\displaystyle {\mathcal {C}}_{j}(x)}$

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

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

• L = DSPACE ( O (журнал  п ))
• PSPACE =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• EXPSPACE =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

Модели машин [ править ]

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

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

Теорема об иерархии [ править ]

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

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

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

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

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

${\displaystyle {\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. Zbl  1193.68112 .

Внешние ссылки [ править ]

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