DSPACE

У рачунарској теорији сложености, DSPACE или SPACE, је рачунарски ресурс који описује ресурс меморијског простора за детерминистичку Тјурингову машину. DSPACE представља укупну количину меморијског простора који је неопходан „нормалном“, физичком рачунару да би решио задати проблем са задатим алгоритмом. DSPACE је једна од најбоље изучених мера сложености, пошто блиско кореспондира са важним реалним ресурсом: количином физичке меморије рачунара потребне за извршење задатог програма.

Класе сложености

Мера DSPACE се користи за дефинисање класа сложености, скупова свих проблема одлучивања који који могу да буду решени коришћењем одређеног меморијског простора. За сваку функцију f(n), постоји класа сложености SPACE(f(n)), скуп проблема одлучивања који могу да буду решени помоћу детерминистичке Тјурингове машине коришћењем простора O(f(n)). Овде не постоји ограничење времена извршења, иако могу да постоје одређене рестрикције везане за друге мере сложености (као на пример алтернације). Неколико важних класа сложености је дефинисано у односу на DSPACE. Оне укључују:

• REG = DSPACE(O(1)), где је REG класа регуларних језика. У ствари, REG = DSPACE(o(log log n)) (што значи да је Ω(log log n) простор потребан да би се препознао било који нерегуларни језик).

Доказ: претпоставимо да постоји нерегуларни језик L ∈ DSPACE(s(n)) за s(n) = o(log log n). Нека је M Тјурингова машина која одлучује о L у простору s(n). Према нашој претпоставци M ∉ DSPACE(O(1)), тако да за сваки произвољни k ∈ $\mathbb {N}$ , постоји улаз за M који захтева више простора него k. Нека је x улаз најмање величине означене са n, који захтева више простора од k и нека је скуп свих конфигурација M за улаз x. Пошто је M ∈ DSPACE(s(n)), онда је $|{\mathcal {C}}|\leq 2^{c.s(n)}$ = o(log n), где је c константа која зависи од M.

Нека S означава скуп свих могућих прелазних секвенци M за x. Приметимо да је дужина прелазне секвенце M за x највише: $|{\mathcal {C}}|$: ако је дуже од тога, онда ће се нека конфигурација поновљати и M ће отићи у бесконачну петљу. Постоји, такође, највише $|{\mathcal {C}}|$: могућности за сваки елемент прелазне секвенце тако да је број различитих прелазних секвенци M за x:

$|S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c.s(n)})^{2^{c.s(n)}}=2^{c.s(n).2^{c.s(n)}}<2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}}=o(n)$

Према принципу Дирихлеа (негде се зове и принцип голубарника и принцип сандука) постоје индекси i < j такви да је ${\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)$ , где су ${\mathcal {C}}_{i}(x)$ и ${\mathcal {C}}_{j}(x)$ прелазне секвенце на границама i и j. Нека је x низ који се добија из x уклањањм свих ћелија од i + 1 до j. Машина M се понаша на исти начин за оба улаза: x и x, тако да захтева исти простор за њихову обраду. Ипак, |x' | < |x|, што је у супротности са дефиницијом x. Из овога следи да не постоји језик L који задовољава на почетку усвојене претпоставке. Горња теорема имплицира потребу за претпоставком да постоји просторно-конструктивна функција у теореми о хијерархији простора.

• L = DSPACE(O(log n))
• PSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})$
• EXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})$

Модели машина

DSPACE се традиционално мери на детерминистичкој Тјуринговој машини. Неколико важних просторних класа сложености су сублинеарне, то јест мање су од величине улаза. Тако, коришћење алгоритама за утврђивање величине улаза и излаза неће довести до тачног податка о употребљеној меморији. Ово се решава дефинисањем Тјурингове машине са више низова и улазом и излазом, која је стандардна Тјурингова машина са више трака, осим што на улазну траку не сме никада да се уписује и са излазне траке се никада не чита. То омогућава да класе мањег простора, као што је L (логаритамски простор) буду дефинисане у односу на количину простора које користе све радне траке (искључујући специјалне улазне и излазне траке). Пошто многи симболи могу да се упакују у један употребом одговарајуће снаге азбуке, за свако c ≥ 1 и f такво да је f(n) ≥ 1, класа језика препознатљивих у простору c f(n) је иста као и класа језика препознатљивих у простору f(n). Ово оправдава употребу велико О нотације у дефиницијама.

Теорема о хијерархији

Теорема о хијерархији простора показује да за сваку просторно конструктивну функцију , постоји неки језик L који је одлучив у простору $f:\mathbb {N} \to \mathbb {N}$ , али не и у простору $O(f(n))$ but not in space $o(f(n))$.

Релације према другим класама сложености

DSPACE је детерминистички пар NSPACE, класе меморијског простора на недетерминистичкој Тјуринговој машини. Према теориме Севича имамо да је:

${\mbox{DSPACE}}[s(n)]\subseteq {\mbox{NSPACE}}[s(n)]\subseteq {\mbox{DSPACE}}[(s(n))^{2}].$

NTIME је у односу са DSPACE на следећи начин: за сваку временски конруктивну функцију t(n), имамо;

${\mbox{NTIME}}(t(n))\subseteq {\mbox{DSPACE}}(t(n))$.