Просторова складність

Просторова складність алгоритму чи комп'ютерної програми — обсяг пам'яті, необхідний для розв'язання екземпляра обчислювальної задачі як функція характеристик вхідних даних. Це пам'ять, необхідна алгоритму, поки він не завершиться повністю.

Подібно до часової складності, просторова складність часто виражається асимптотично у O-нотації, наприклад: $O(n),$ $O(n\log n),$ $O(n^{\alpha }),$ $O(2^n),$ тощо, де Шаблон:Mvar є характеристикою вхідних даних, що впливають на просторову складність.

Класи просторової складності

Аналогічно класам часової складності DTIME(f(n)) та NTIME(f(n)), класи просторової складності DSPACE(f(n)) та NSPACE(f(n)) — це набори мов, які можна визначити детермінованими (відповідно, недетермінованими) машинами Тьюрінга, які використовують $O(f(n))$ простір. Класи складності PSPACE і NPSPACE дозволяють $f$ бути будь-яким многочленом, аналогічно P і NP. Тобто,

$𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{c\in {\mathbb{Z}}^{+}}𝖣𝖲𝖯𝖠𝖢𝖤(n^c)$

і

$𝖭𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{c\in {\mathbb{Z}}^{+}}𝖭𝖲𝖯𝖠𝖢𝖤(n^c)$

Відношення між класами

Теорема про просторову ієрархію стверджує, що для всіх Шаблон:Не перекладено функцій $f(n)$, існує задача, яку можна розв'зати машиною з $f(n)$ простором пам'яті, але яка не може бути розв'язана машиною з асимптотично меншим за $f(n)$ простором.

Мають місце наведені нижче обмеження між класами складності.

$𝖣𝖳𝖨𝖬𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖳𝖨𝖬𝖤\left(2^{O\left(f\left(n\right)\right)}\right)$

Крім того, теорема Савича дає зворотне обмеження, що якщо $f\in \mathrm{\Omega }(\log (n))$,

$𝖭𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤\left({\left(f\left(n\right)\right)}^2\right).$

Як прямий наслідок: $𝖯𝖲𝖯𝖠𝖢𝖤=𝖭𝖯𝖲𝖯𝖠𝖢𝖤$. Цей результат дивує, оскільки свідчить про те, що недетермінованість може зменшити простір, необхідний для розв'язання задачи, лише на невеликий об'єм пам'яті. На відміну від цього, гіпотеза експоненціального часу припускає, що для часової складності може існувати експоненціальний розрив між детермінованою та недетермінованою складністю.

Теорема Іммермана — Селепчєнні стверджує, що знову для $f\in \mathrm{\Omega }(\log (n))$, $𝖭𝖲𝖯𝖠𝖢𝖤(f(n))$ закрито на доповнення. Це свідчить про ще одну якісну різницю між класами часової і просторової складності, оскільки недетерміновані класи часової складності, як вважають, не закриваються від доповнення; наприклад, передбачається, що NP ≠ co-NP.