НСПАСЕ
В теории сложности вычислений недетерминированное пространство или NSPACE — это вычислительный ресурс, описывающий пространство памяти для недетерминированной машины Тьюринга . Это недетерминированный аналог DSPACE .
Классы сложности [ править ]
Мера NSPACE используется для определения класса сложности , решения которого могут быть определены недетерминированной машиной Тьюринга . Класс сложности NSPACE( f ( n )) — это набор задач решения , которые могут быть решены недетерминированной машиной Тьюринга , M используя пространство O ( f ( n )), где n — длина входных данных. [1]
Несколько важных классов сложности могут быть определены в терминах NSPACE . К ним относятся:
- REG = DSPACE( O (1)) = NSPACE( O (1)), где REG — класс регулярных языков (недетерминизм не добавляет мощности в постоянном пространстве).
- NL = NSPACE( O (log n ))
- CSL = NSPACE( O ( n )), где CSL — класс контекстно-зависимых языков .
- PSPACE = NPSPACE =
- EXPSPACE = NEXPSPACE =
Теорема Иммермана -Селепшеньи утверждает, что NSPACE( s ( n )) замкнуто относительно дополнения для любой функции s ( n ) ≥ log n .
Дальнейшее обобщение — ASPACE, определяемое с помощью чередующихся машин Тьюринга .
Связь с другими классами сложности [ править ]
ДСПЕЙС [ править ]
NSPACE — это недетерминированный аналог DSPACE , класса пространства памяти на детерминированной машине Тьюринга . Сначала по определению, затем по теореме Савича имеем следующее:
![{\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2 }].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecd4ae2f63770c1eb464eab1a65c457990883b00)
Время [ править ]
NSPACE также можно использовать для определения временной сложности детерминированной машины Тьюринга по следующей теореме:
Если выбор языка L определяется в пространстве S ( n ) (где S ( n ) ≥ log n ) с помощью недетерминированной TM, то существует константа C такая, что решение L определяется за время O ( C С ( п ) ) детерминированным. [2]
Ограничения [ править ]
Мера пространственной сложности с точки зрения DSPACE полезна, поскольку она представляет собой общий объем памяти, который понадобится реальному компьютеру для решения данной вычислительной задачи с помощью данного алгоритма . Причина в том, что DSPACE описывает сложность пространства, используемого детерминированными машинами Тьюринга , которые могут представлять собой настоящие компьютеры. С другой стороны, NSPACE описывает пространственную сложность недетерминированных машин Тьюринга , которые бесполезны при попытке представить реальные компьютеры. По этой причине полезность NSPACE ограничена для реальных приложений.
Ссылки [ править ]
- ^ Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.) . Курсовая технология. стр. 303–304 . ISBN 978-0-534-95097-2 .
- ^ Годдард, Уэйн (2008). Введение в теорию вычислений . Jones and Bartlett Publishers, Inc. с. 183. ИСБН 978-0-7637-4125-9 .