DSPACE
Nella teoria della complessità , DSPACE (o SPACE ) designa una famiglia di classi di complessità caratterizzate dalla loro complessità spaziale su una macchina di Turing deterministica.
Più precisamente, è la classe dei problemi decisionali che, per un input dimensionale , può essere decisa da una deterministica macchina di Turing operante nello spazio .
DSPAVSE(f(non)){\ displaystyle {\ mathsf {DSPACE}} (f (n))}non{\ displaystyle n}O(f(non)){\ displaystyle {\ mathcal {O}} (f (n))}
Definizioni
Le classi di complessità L , PSPACE e EXPSPACE sono definite dalla famiglia DSPACE:
L=DSPAVSE(O(lognon)){\ displaystyle {\ mathsf {L}} = {\ mathsf {DSPACE}} ({\ mathcal {O}} (\ log n))}PSPAVSE=⋃K∈NONDSPAVSE(nonK){\ displaystyle {\ mathsf {PSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DSPACE}} (n ^ {k})}EXPSPAVSE=⋃K∈NONDSPAVSE(2nonK){\ displaystyle {\ mathsf {EXPSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DSPACE}} \ left (2 ^ {n ^ {k}} \ right)}Le lingue regolari possono essere definite come . In effetti, abbiamo anche : lo spazio più piccolo richiesto per riconoscere un linguaggio non razionale lo è , e qualsiasi macchina di Turing nello spazio riconosce un linguaggio razionale.
REG=DSPAVSE(O(1)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {O}} (1))}REG=DSPAVSE(o(loglognon)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {o}} (\ log \ log n))}O(loglognon){\ displaystyle {\ mathcal {O}} (\ log \ log n)}o(loglognon){\ displaystyle o (\ log \ log n)}
Gerarchia nello spazio
Informalmente, il teorema della gerarchia nello spazio indica che avere più spazio consente di decidere più problemi. Più precisamente, per tutte le funzioni e tali che e sia costruibile nello spazio , si verifica il seguente rigoroso inserimento:
f{\ displaystyle f}g{\ displaystyle g}f=o(g){\ displaystyle f = o (g)}g{\ displaystyle g}
DSPAVSE(f(non))⊊DSPAVSE(g(non)){\ displaystyle {\ mathsf {DSPACE}} (f (n)) \ subsetneq {\ mathsf {DSPACE}} (g (n))}
Collegamenti con altre classi
Il teorema Savitch collega DSPACE alle classi di complessità in memoria non deterministica NSPACE le seguenti inclusioni per qualsiasi spazio di costruzione di funzioni come :
f{\ displaystyle f}f(non)≥lognon{\ displaystyle f (n) \ geq \ log n}
DSPAVSE(f(non))⊆NONSPAVSE(f(non))⊆DSPAVSE(f(non)2){\ Displaystyle {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DSPACE}} \ left (f (n) ^ {2 } \ giusto)}Una conseguenza è che PSPACE = NPSPACE .
Inoltre, DSPACE è collegato alle classi di complessità temporale DTIME e NTIME dalle seguenti inclusioni, per qualsiasi funzione costruibile nello spazio:
f{\ displaystyle f}
NONTioME(f(non))⊆DSPAVSE(f(non))⊆NONSPAVSE(f(non))⊆DTioME(2O(f(non))){\ Displaystyle {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ left (2 ^ {{\ mathcal {O}} (f (n))} \ right)}
Note e riferimenti
Riferimenti
-
( entra ) Andrzej Szepietowski , Macchine di Turing con spazio sublogaritmico , Springer Science + Business Media ,29 agosto 1994, 114 p. ( ISBN 978-3-540-58355-4 , leggi online ) , p. 28
Bibliografia
-
(en) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20 aprile 2009, 579 p. ( ISBN 978-0-521-42426-4 , leggi in linea ).
-
Sylvain Perifel, Complessità algoritmica , Éditions Ellipses ,22 aprile 2014, 432 p. ( ISBN 978-2-729-88692-9 , leggi online ).