НСПАСЕ

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

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

Мера NSPACE используется для определения класса сложности , решения которого могут быть определены недетерминированной машиной Тьюринга . Класс сложности NSPACE( f ( n )) — это набор задач решения , которые могут быть решены недетерминированной машиной Тьюринга , M используя пространство O ( f ( n )), где n — длина входных данных.

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

• REG = DSPACE( O (1)) = NSPACE( O (1)), где REG — класс регулярных языков (недетерминизм не добавляет мощности в постоянном пространстве).
• NL = NSPACE( O (log n ))
• CSL = NSPACE( O ( n )), где CSL — класс контекстно-зависимых языков .
• PSPACE = NPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$
• EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$

Теорема Иммермана -Селепшеньи утверждает, что NSPACE( s ( n )) замкнуто относительно дополнения для любой функции s ( n ) ≥ log n .

Дальнейшее обобщение — ASPACE, определяемое с помощью чередующихся машин Тьюринга .

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

ДСПЕЙС

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

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

Время

NSPACE также можно использовать для определения временной сложности детерминированной машины Тьюринга по следующей теореме:

Если выбор языка L определяется в пространстве S ( n ) (где S ( n ) ≥ log n ) с помощью недетерминированной TM, то существует константа C такая, что решение L определяется за время O ( C ^{С ( п )} ) детерминистическим.

Ограничения

Мера пространственной сложности с точки зрения DSPACE полезна, поскольку она представляет собой общий объем памяти, который понадобится реальному компьютеру для решения данной вычислительной задачи с помощью данного алгоритма . Причина в том, что DSPACE описывает сложность пространства, используемого детерминированными машинами Тьюринга , которые могут представлять собой настоящие компьютеры. С другой стороны, NSPACE описывает пространственную сложность недетерминированных машин Тьюринга , которые бесполезны при попытке представить реальные компьютеры. По этой причине полезность NSPACE ограничена для реальных приложений.

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

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