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

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

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

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

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

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

і

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

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

Теорема про просторову ієрархію стверджує, що для всіх просторово сконструйованих^[en] функцій ${\displaystyle f(n)}$, існує задача, яку можна розв'зати машиною з ${\displaystyle f(n)}$ простором пам'яті, але яка не може бути розв'язана машиною з асимптотично меншим за ${\displaystyle f(n)}$ простором.

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

${\displaystyle {\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)}$

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

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

Як прямий наслідок: ${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}}$. Цей результат дивує, оскільки свідчить про те, що недетермінованість може зменшити простір, необхідний для розв'язання задачи, лише на невеликий об'єм пам'яті. На відміну від цього, гіпотеза експоненціального часу припускає, що для часової складності може існувати експоненціальний розрив між детермінованою та недетермінованою складністю.

Теорема Іммермана — Селепчєнні стверджує, що знову для ${\displaystyle f\in \Omega (\log(n))}$, ${\displaystyle {\mathsf {NSPACE}}(f(n))}$ закрито на доповнення. Це свідчить про ще одну якісну різницю між класами часової і просторової складності, оскільки недетерміновані класи часової складності, як вважають, не закриваються від доповнення; наприклад, передбачається, що NP ≠ co-NP.[3][4]

Примітки

1. Kuo, Way; Zuo, Ming J. (2003), Optimal Reliability Modeling: Principles and Applications, John Wiley & Sons, с. 62, ISBN 9780471275459, архів оригіналу за 11 серпня 2021, процитовано 17 березня 2021
2. Arora, Sanjeev; Barak, Boaz (2007), Computational Complexity : A Modern Approach (PDF) (вид. draft), с. 76, ISBN 9780511804090, архів оригіналу (PDF) за 20 березня 2021, процитовано 17 березня 2021
3. Immerman, Neil (1988), Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, 17 (5): 935—938, doi:10.1137/0217058, MR 0961049, архів оригіналу (PDF) за 7 лютого 2012, процитовано 17 березня 2021
4. Szelepcsényi, Róbert (1987), The method of forcing for nondeterministic automata, Bulletin of the EATCS, 33: 96—100