Космическая сложность

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

Подобно временной сложности , пространственная сложность часто выражается асимптотически в нотации большого O , например, и т. Д., Где $n$ - характеристика входных данных, влияющих на пространственную сложность. ${\ Displaystyle О (п),}$ ${\ Displaystyle О (п \ журнал п),}$ ${\ Displaystyle О (п ^ {\ альфа}),}$ ${\ displaystyle O (2 ^ {n}),}$

Классы космической сложности [ править ]

Аналогично классам временной сложности DTIME (f (n)) и NTIME (f (n)) , классы сложности DSPACE (f (n)) и NSPACE (f (n)) представляют собой наборы языков, которые разрешимы с помощью детерминированного ( соответственно, недетерминированные) машины Тьюринга , использующие пространство. Классы сложности PSPACE и NPSPACE позволяют быть любым многочленом, аналогично P и NP . То есть, ${\ Displaystyle О (е (п))}$ ${\ displaystyle f}$

{\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}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DTIME}}\left(2^{O\left(f\left(n\right)\right)}\right)

Кроме того, теорема Сэвича дает обратное включение, что если , $f\in \Omega (\log(n))$

{\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).

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

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

LOGSPACE [ править ]

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

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

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

Ссылки [ править ]

^ Куо, Путь; Цзо, Мин Дж. (2003), Оптимальное моделирование надежности: принципы и приложения , John Wiley & Sons, стр. 62, ISBN 9780471275459
^ Арора, Санджив ; Барак, Боаз (2007), Вычислительная сложность: современный подход (PDF) (черновой вариант), стр. 76, ISBN 9780511804090
^ Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, DOI : 10,1137 / 0217058 , MR 0961049
^ Szelepcsényi, Роберт (1987), "Метод принуждения для недетерминированных автоматов", Бюллетень EATCS , 33 : 96–100
^ Нисан, Ноам (1992), "RL ⊆ SC", Труды 24 - го ACM симпозиум по теории вычислительных (КТВЗР '92) , Виктория, Британская Колумбия, Канада, С. 619-623,. DOI : 10,1145 / 129712,129772.
^ Рейнгольд, Омер ; Тревизан, Лука ; Вадхан, Салил (2006), «Псевдослучайные прогулки по регулярным орграфам и проблема RL vs. L» (PDF) , STOC'06: Материалы 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 457– 466, DOI : 10,1145 / 1132516,1132583 , МР 2277171

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

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

[3] Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, DOI : 10,1137 / 0217058 , MR 0961049

[4] Szelepcsényi, Роберт (1987), "Метод принуждения для недетерминированных автоматов", Бюллетень EATCS , 33 : 96–100

[5] Нисан, Ноам (1992), "RL ⊆ SC", Труды 24 - го ACM симпозиум по теории вычислительных (КТВЗР '92) , Виктория, Британская Колумбия, Канада, С. 619-623,. DOI : 10,1145 / 129712,129772.

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

[1]