DSPACE

U računarskoj teoriji složenosti, DSPACE ili SPACE, je računarski resurs koji opisuje resurs memorijskog prostora za determinističku Tjuringovu mašinu. DSPACE predstavlja ukupnu količinu memorijskog prostora koji je neophodan „normalnom“, fizičkom računaru da bi rešio zadati problem sa zadatim algoritmom. DSPACE je jedna od najbolje izučenih mera složenosti, pošto blisko korespondira sa važnim realnim resursom: količinom fizičke memorije računara potrebne za izvršenje zadatog programa.

Klase složenosti

Mera DSPACE se koristi za definisanje klasa složenosti, skupova svih problema odlučivanja koji koji mogu da budu rešeni korišćenjem određenog memorijskog prostora. Za svaku funkciju f(n), postoji klasa složenosti SPACE(f(n)), skup problema odlučivanja koji mogu da budu rešeni pomoću determinističke Tjuringove mašine korišćenjem prostora O(f(n)). Ovde ne postoji ograničenje vremena izvršenja, iako mogu da postoje određene restrikcije vezane za druge mere složenosti (kao na primer alternacije). Nekoliko važnih klasa složenosti je definisano u odnosu na DSPACE. One uključuju:

• REG = DSPACE(O(1)), gde je REG klasa regularnih jezika. U stvari, REG = DSPACE(o(log log n)) (što znači da je Ω(log log n) prostor potreban da bi se prepoznao bilo koji neregularni jezik).

Dokaz: pretpostavimo da postoji neregularni jezik L ∈ DSPACE(s(n)) za s(n) = o(log log n). Neka je M Tjuringova mašina koja odlučuje o L u prostoru s(n). Prema našoj pretpostavci M ∉ DSPACE(O(1)), tako da za svaki proizvoljni k ∈ $\mathbb {N}$ , postoji ulaz za M koji zahteva više prostora nego k. Neka je x ulaz najmanje veličine označene sa n, koji zahteva više prostora od k i neka je skup svih konfiguracija M za ulaz x. Pošto je M ∈ DSPACE(s(n)), onda je $|{\mathcal {C}}|\leq 2^{c.s(n)}$ = o(log n), gde je c konstanta koja zavisi od M.

Neka S označava skup svih mogućih prelaznih sekvenci M za x. Primetimo da je dužina prelazne sekvence M za x najviše: $|{\mathcal {C}}|$: ako je duže od toga, onda će se neka konfiguracija ponovljati i M će otići u beskonačnu petlju. Postoji, takođe, najviše $|{\mathcal {C}}|$: mogućnosti za svaki element prelazne sekvence tako da je broj različitih prelaznih sekvenci M za 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)$

Prema principu Dirihlea (negde se zove i princip golubarnika i princip sanduka) postoje indeksi i < j takvi da je ${\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)$ , gde su ${\mathcal {C}}_{i}(x)$ i ${\mathcal {C}}_{j}(x)$ prelazne sekvence na granicama i i j. Neka je x niz koji se dobija iz x uklanjanjm svih ćelija od i + 1 do j. Mašina M se ponaša na isti način za oba ulaza: x i x, tako da zahteva isti prostor za njihovu obradu. Ipak, |x' | < |x|, što je u suprotnosti sa definicijom x. Iz ovoga sledi da ne postoji jezik L koji zadovoljava na početku usvojene pretpostavke. Gornja teorema implicira potrebu za pretpostavkom da postoji prostorno-konstruktivna funkcija u teoremi o hijerarhiji prostora.

• 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}})$

Modeli mašina

DSPACE se tradicionalno meri na determinističkoj Tjuringovoj mašini. Nekoliko važnih prostornih klasa složenosti su sublinearne, to jest manje su od veličine ulaza. Tako, korišćenje algoritama za utvrđivanje veličine ulaza i izlaza neće dovesti do tačnog podatka o upotrebljenoj memoriji. Ovo se rešava definisanjem Tjuringove mašine sa više nizova i ulazom i izlazom, koja je standardna Tjuringova mašina sa više traka, osim što na ulaznu traku ne sme nikada da se upisuje i sa izlazne trake se nikada ne čita. To omogućava da klase manjeg prostora, kao što je L (logaritamski prostor) budu definisane u odnosu na količinu prostora koje koriste sve radne trake (isključujući specijalne ulazne i izlazne trake). Pošto mnogi simboli mogu da se upakuju u jedan upotrebom odgovarajuće snage azbuke, za svako c ≥ 1 i f takvo da je f(n) ≥ 1, klasa jezika prepoznatljivih u prostoru c f(n) je ista kao i klasa jezika prepoznatljivih u prostoru f(n). Ovo opravdava upotrebu veliko O notacije u definicijama.

Teorema o hijerarhiji

Teorema o hijerarhiji prostora pokazuje da za svaku prostorno konstruktivnu funkciju , postoji neki jezik L koji je odlučiv u prostoru $f:\mathbb {N} \to \mathbb {N}$ , ali ne i u prostoru $O(f(n))$ but not in space $o(f(n))$.

Relacije prema drugim klasama složenosti

DSPACE je deterministički par NSPACE, klase memorijskog prostora na nedeterminističkoj Tjuringovoj mašini. Prema teorime Seviča imamo da je:

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

NTIME je u odnosu sa DSPACE na sledeći način: za svaku vremenski konruktivnu funkciju t(n), imamo;

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