Пространственная сложность

Пространственная сложность алгоритма в или структуры данных — это объем памяти, необходимый для решения экземпляра вычислительной задачи, зависимости от характеристик входных данных. Это память, необходимая алгоритму до его полного выполнения. ^[1] Сюда входит пространство памяти, используемое его входами, называемое входным пространством , и любая другая (вспомогательная) память, которую он использует во время выполнения, которая называется вспомогательным пространством .

Подобно временной сложности , пространственная сложность часто выражается асимптотически в обозначении большого О , например: $O(n),$ $O(n\log n),$ $O(n^{\alpha }),$ $O(2^{n}),$ и т. д., где $n$ — характеристика входных данных, влияющая на сложность пространства.

Классы пространственной сложности

Аналогично классам временной сложности DTIME(f(n)) и NTIME(f(n)) классы сложности DSPACE(f(n)) и NSPACE(f(n)) представляют собой наборы языков, которые разрешимы детерминированными методами ( соответственно, недетерминированные) Машины Тьюринга , использующие $O(f(n))$ космос. Классы сложности PSPACE и NPSPACE позволяют $f$ быть любым полиномом, аналогично P и NP . То есть, ${\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})$ и ${\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})$

Отношения между классами

Теорема о пространственной иерархии утверждает, что для всех пространственно-конструируемых функций $f(n),$ существует проблема, которую можно решить с помощью машины с $f(n)$ памяти, но не может быть решена машиной с асимптотически меньшими $f(n)$ космос.

Имеют место следующие ограничения между классами сложности. ^[2] ${\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)$

Более того, теорема Савича дает обратное утверждение: если $f\in \Omega (\log(n)),$ ${\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).$

Как прямое следствие, ${\mathsf {PSPACE}}={\mathsf {NPSPACE}}.$ Этот результат удивителен, поскольку предполагает, что недетерминизм может лишь незначительно уменьшить пространство, необходимое для решения проблемы. Напротив, гипотеза экспоненциального времени предполагает, что для временной сложности может существовать экспоненциальный разрыв между детерминированной и недетерминированной сложностью.

Теорема Иммермана – Селепшени утверждает, что опять же для $f\in \Omega (\log(n)),$ ${\mathsf {NSPACE}}(f(n))$ замкнуто относительно дополнения. Это показывает еще одно качественное различие между классами временной и пространственной сложности, поскольку недетерминированные классы временной сложности не считаются закрытыми при дополнении; например, предполагается, что NP ≠ co-NP . ^[3]^[4]

ПРОСТРАНСТВО ЖУРНАЛА

L или LOGSPACE — это набор задач, которые может решить детерминированная машина Тьюринга, используя только $O(\log n)$ пространство памяти относительно размера ввода. Даже один счетчик, который может индексировать всю $n$ -битный ввод требует $\log n$ пространство, поэтому алгоритмы LOGSPACE могут поддерживать только постоянное количество счетчиков или других переменных одинаковой битовой сложности.

LOGSPACE и другие сублинейные пространственные сложности полезны при обработке больших данных, которые не могут поместиться в оперативную память компьютера . Они связаны с алгоритмами потоковой передачи , но ограничивают только объем используемой памяти, в то время как алгоритмы потоковой передачи имеют дополнительные ограничения на то, как входные данные подаются в алгоритм. Этот класс также находит применение в области псевдослучайности и дерандомизации , где исследователи рассматривают открытую проблему того, является ли L = RL . ^[5]^[6]

Соответствующий класс сложности недетерминированного пространства — NL .

Сложность вспомогательного пространства

Термин Вспомогательное пространство относится к пространству, отличному от того, которое используется для ввода. Сложность вспомогательного пространства можно формально определить в терминах машины Тьюринга с отдельной входной лентой , на которую нельзя записывать, а только читать, и обычной рабочей лентой, на которую можно записывать. Затем сложность вспомогательного пространства определяется (и анализируется) с помощью рабочей ленты. Например, рассмотрим поиск в глубину сбалансированного двоичного дерева с $n$ узлы: сложность его вспомогательного пространства равна $\Theta (\log n).$

См. также

Анализ алгоритмов - Исследование ресурсов, используемых алгоритмом.
Теория сложности вычислений . Неотъемлемая сложность вычислительных задач.
Вычислительный ресурс — что-то, что необходимо компьютеру для решения проблемы, например этапы обработки или память.

Ссылки

^ Куо, Уэй; Цзо, Мин Дж. (2003), Моделирование оптимальной надежности: принципы и приложения , John Wiley & Sons, стр. 62, ISBN 9780471275459
^ Арора, Санджив ; Барак, Боаз (2007), Сложность вычислений: современный подход (PDF) (проект), стр. 76, ISBN 9780511804090
^ Иммерман, Нил (1988), «Недетерминированное пространство закрыто при дополнении» (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137/0217058 , MR 0961049
^ Селепсени, Роберт (1987), «Метод форсирования недетерминированных автоматов», Бюллетень EATCS , 33 : 96–100
^ Нисан, Ноам (1992), «RL ⊆ SC», Труды 24-го симпозиума ACM по теории вычислений (STOC '92) , Виктория, Британская Колумбия, Канада, стр. 619–623, doi : 10.1145/129712.129772 , ISBN 0-89791-511-9 , S2CID 11651375 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
^ Рейнгольд, Омер ; Тревизан, Лука ; Вадхан, Салил (2006), «Псевдослучайные блуждания по регулярным орграфам и проблема RL и L» (PDF) , STOC'06: Материалы 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 457– 466, номер домена : 10.1145/1132516.1132583 , ISBN 1-59593-134-1 , МР 2277171 , S2CID 17360260

[1] Куо, Уэй; Цзо, Мин Дж. (2003), Моделирование оптимальной надежности: принципы и приложения , John Wiley & Sons, стр. 62, ISBN 9780471275459

[2] Арора, Санджив ; Барак, Боаз (2007), Сложность вычислений: современный подход (PDF) (проект), стр. 76, ISBN 9780511804090

[3] Иммерман, Нил (1988), «Недетерминированное пространство закрыто при дополнении» (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137/0217058 , MR 0961049

[4] Селепсени, Роберт (1987), «Метод форсирования недетерминированных автоматов», Бюллетень EATCS , 33 : 96–100

[5] Нисан, Ноам (1992), «RL ⊆ SC», Труды 24-го симпозиума ACM по теории вычислений (STOC '92) , Виктория, Британская Колумбия, Канада, стр. 619–623, doi : 10.1145/129712.129772 , ISBN 0-89791-511-9 , S2CID 11651375 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .

[6] Рейнгольд, Омер ; Тревизан, Лука ; Вадхан, Салил (2006), «Псевдослучайные блуждания по регулярным орграфам и проблема RL и L» (PDF) , STOC'06: Материалы 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 457– 466, номер домена : 10.1145/1132516.1132583 , ISBN 1-59593-134-1 , МР 2277171 , S2CID 17360260

[1]

[2]

[3]

[4]

[5]

[6]