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

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

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

Классы космической сложности

Аналогично классам временной сложности ДВРЕМЯ (f (n)) и NTIME (f (n)), классы сложности DSPACE (f (n)) и NSPACE (f (n)) - это множества языков, которые разрешимы детерминированными (соответственно недетерминированными) Машины Тьюринга это использование ${ Displaystyle О (е (п))}$ Космос. Классы сложности PSPACE и NPSPACE позволять ${ displaystyle f}$ быть любым полиномом, аналогично п и НП. То есть,

${ displaystyle { mathsf {PSPACE}} = bigcup _ {c in mathbb {Z} ^ {+}} { mathsf {DSPACE}} (n ^ {c})}$

и

${ displaystyle { mathsf {NPSPACE}} = bigcup _ {c in mathbb {Z} ^ {+}} { mathsf {NSPACE}} (n ^ {c})}$

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

В теорема пространственной иерархии заявляет, что для всех пространственно-конструктивные функции ${ Displaystyle f (п)}$, существует проблема, которую может решить машина с ${ Displaystyle f (п)}$ объем памяти, но не может быть решен машиной с асимптотически меньше, чем ${ Displaystyle f (п)}$Космос.

Имеются следующие ограничения между классами сложности.^[2]

${ Displaystyle { mathsf {DTIME}} влево (е влево (п вправо) вправо) substeq { mathsf {DSPACE}} влево (е влево (п вправо) вправо) substeq { mathsf {NSPACE}} left (f left (n right) right) substeq { mathsf {DTIME}} left (2 ^ {O left (f left (n right) right) }верно)}$

Более того, Теорема савича дает обратное включение, что если ${ Displaystyle е в Омега ( журнал (п))}$,

${ Displaystyle { mathsf {NSPACE}} влево (е влево (п вправо) вправо) substeq { mathsf {DSPACE}} влево ( влево (е влево (п вправо) вправо) ^ {2} right).}$

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

В Теорема Иммермана – Селепсеньи заявляет, что снова для ${ Displaystyle е в Омега ( журнал (п))}$, ${ Displaystyle { mathsf {NSPACE}} (е (п))}$ закрыт на дополнение. Это показывает еще одно качественное различие между классами временной и пространственной сложности, поскольку недетерминированные классы временной сложности не считаются закрытыми при дополнении; например, предполагается, что NP ≠ со-НП.^[3][4]

LOGSPACE

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

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

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

Рекомендации