NSPACE - NSPACE

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

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

Мера NSPACE используется для определения класс сложности решения которого могут быть определены недетерминированная машина Тьюринга. В класс сложности NSPACE (ж(п)) - множество проблемы решения это может быть решено недетерминированная машина Тьюринга, M, используя пространство О(ж(п)), где п - длина ввода.^[1]

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

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

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

Дальнейшее обобщение - это ASPACE, определяемый как чередующиеся машины Тьюринга.

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

DSPACE

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

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

Время

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

Если язык L решено в космосе S(п) (где S(п) ≥ журнал п) недетерминированной ТМ, то существует постоянная C такой, что L решено вовремя О(C^S(п)) на детерминированный.^[2]

Ограничения

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

использованная литература

1. Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). Курсовая технология. стр.303 –304. ISBN  978-0-534-95097-2.
2. Годдард, Уэйн (2008). Введение в теорию вычислений. Jones and Bartlett Publishers, Inc. стр. 183. ISBN  978-0-7637-4125-9.

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

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