DПРОСТРАНСТВО
-
Определение DSPACE
- DSPACE — это вычислительный ресурс, описывающий объем памяти для детерминированной машины Тьюринга.
- Он измеряет общий объем памяти, необходимый для решения задачи с использованием заданного алгоритма.
-
Классы сложности DSPACE
- Для каждой функции f(n) существует класс сложности (f(n)), описывающий задачи, решаемые с использованием пространства O(f(n)).
- Нет ограничений на время вычислений, но могут быть ограничения на другие показатели сложности.
-
Важные классы сложности DSPACE
- REG — это класс обычных языков, который может быть решен с использованием пространства O(1).
- Доказательство теоремы о нерегулярных языках показывает, что для любого нерегулярного языка требуется пространство Ω(log log n).
-
Пространственная иерархия
- Теорема о пространственной иерархии утверждает, что для каждой пространственно-конструктивной функции f(n) существует язык L, разрешимый в пространстве O(f(n)), но не в пространстве o(f(n)).
-
Связь с другими классами сложности
- DSPACE является детерминированным аналогом NSPACE, класса памяти в недетерминированной машине Тьюринга.
- Согласно теореме Савича, NTIME связан с DSPACE.
Полный текст статьи: