Оглавление
ПРОСТРАНСТВО N
-
Определение NSPACE
- NSPACE – это недетерминированное пространство, аналог DSPACE.
- Используется для определения классов сложности, решаемых недетерминированными машинами Тьюринга.
-
Классы сложности NSPACE
- REG = DSPACE(O(1)) = NSPACE(O(1)) – класс обычных языков.
- NL = NSPACE(O(log n)) – класс контекстно-зависимых языков.
- CSL = NSPACE(O(n)) – класс контекстно-свободных языков.
- PSPACE = NPSPACE = ⋃k∈NNSPACE(nk) – класс разрешимых языков.
- EXPSPACE = СЛЕДУЮЩЕЕ ПРОСТРАНСТВО = ⋃k∈NNSPACE(2nk) – класс экспоненциально разрешимых языков.
-
Теорема Иммермана-Шелепчени
- NSPACE(s(n)) замкнуто относительно дополнения для функций s(n) ≥ log n.
-
Связь с DSPACE
- NSPACE является недетерминированным аналогом DSPACE.
- DSPACE[s(n)] ⊆ NSPACE[s(n)] ⊆ DSPACE[(s(n))2].
-
Временная сложность
- Если язык L определяется в пространстве S(n) недетерминированным TM, то L определяется во времени O(CS(n)) детерминированным TM.
-
Ограничения NSPACE
- NSPACE описывает сложность недетерминированных машин Тьюринга, которые не могут быть использованы для моделирования реальных компьютеров.
- Ограничена в полезности для реальных приложений.
-
Рекомендации
- Ссылки на “Зоопарк сложности: NSPACE(f(n))”.
Полный текст статьи: