В теории сложности вычислений недетерминированное пространство или NSPACE - это вычислительный ресурс, описывающий пространство памяти для недетерминированной машины Тьюринга . Это недетерминированный аналог DSPACE .
Классы сложности [ править ]
Мера NSPACE используется для определения класса сложности , решения которого могут быть определены недетерминированной машиной Тьюринга . Класс сложности N-Space ( е ( п )) есть множество проблем решения , которые могут быть решены с помощью недетерминированной машины Тьюринга , М , используя пространство O ( F ( п )), где п есть длина входных данных. [1]
В терминах NSPACE можно определить несколько важных классов сложности . Они включают:
- REG = DSPACE ( O (1)) = NSPACE ( O (1)), где REG - класс обычных языков (недетерминизм не добавляет силы в постоянном пространстве).
- NL = NSPACE ( O (журнал n ))
- CSL = NSPACE ( O ( n )), где CSL - это класс контекстно-зависимых языков .
- PSPACE = NPSPACE =
- EXPSPACE = NEXPSPACE =
Теорема Иммермана – Селепшеньи утверждает, что NSPACE ( s ( n )) замкнут относительно дополнения для любой функции s ( n ) ≥ log n .
Дальнейшее обобщение - это ASPACE, определенный с помощью чередующихся машин Тьюринга .
Связь с другими классами сложности [ править ]
DSPACE [ править ]
NSPACE - это недетерминированный аналог DSPACE , класс пространства памяти на детерминированной машине Тьюринга . Сначала по определению, а затем по теореме Савича , мы имеем следующее:
![{\ displaystyle {\ mathsf {DSPACE}} [s (n)] \ substeq {\ mathsf {NSPACE}} [s (n)] \ substeq {\ 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 S ( n ) ) детерминированным. [2]
Ограничения [ править ]
Измерение сложности пространства в терминах DSPACE полезно, потому что оно представляет собой общий объем памяти, который потребуется фактическому компьютеру для решения данной вычислительной задачи с заданным алгоритмом . Причина в том, что DSPACE описывает сложность пространства, используемого детерминированными машинами Тьюринга , которые могут представлять реальные компьютеры. С другой стороны, NSPACE описывает пространственную сложность недетерминированных машин Тьюринга , которые бесполезны при попытке представить реальные компьютеры. По этой причине полезность NSPACE для реальных приложений ограничена.
Ссылки [ править ]
- ^ Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.) . Курсовая технология. стр. 303 -304. ISBN 978-0-534-95097-2.
- ^ Годдард, Уэйн (2008). Введение в теорию вычислений . Jones and Bartlett Publishers, Inc. стр. 183. ISBN. 978-0-7637-4125-9.
Внешние ссылки [ править ]
- Зоопарк сложности : NSPACE ( f ( n )) .
