EXPSPACE
V teorii složitosti , EXPSPACE je třída problémů rozhodnutelný v exponenciálním prostoru pomocí deterministický Turing stroj .
Formální definice
Pokud nazýváme množinu všech problémů, které lze vyřešit deterministickými Turingovými stroji využívajícími prostor pro funkci o velikosti vstupu , definujeme EXPSPACE pomocí:
PROSTOR(s(ne)){\ displaystyle {\ mbox {SPACE}} (s (n))}Ó(s(ne)){\ displaystyle O (s (n))}s{\ displaystyle s}ne{\ displaystyle n}
EXPSPACE=⋃k∈NEPROSTOR(2nek) .{\ displaystyle {\ mbox {EXPSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {SPACE}} (2 ^ {n ^ {k}}) \.}
Odkazy s jinými třídami
Jak je znázorněno na obrázku vpravo, EXPSPACE obsahuje většinu klasických tříd složitosti. Zejména: NP PSPACE EXPTIME EXPSPACE.
⊆{\ displaystyle \ scriptstyle \ subseteq} ⊆{\ displaystyle \ scriptstyle \ subseteq} ⊆{\ displaystyle \ scriptstyle \ subseteq}
Podle věty o prostorové hierarchii (en) je PSPACE striktně zahrnut do EXPSPACE. Zda je EXPTIME přísnou podmnožinou EXPSPACE, je otevřená otázka.
Podle Savitchovy věty se EXPSPACE rovná NEXPSPACE .
Podle věty Immerman-Szelepcsényi se EXPSPACE rovná co- EXPSPACE.
EXPSPACE je součástí 2-EXPTIME (definováno ).
2-EXPTIME=⋃k∈NE DTIME (22nek){\ displaystyle {\ mbox {2-EXPTIME}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {DTIME}} \ vlevo (2 ^ {2 ^ {n ^ {k}}}} \ že jo)}
EXPSPACE - kompletní problémy
Rozhodovací problém je EXPSPACE-kompletní, pokud je v EXPSPACE a jakýkoli problém EXPSPACE je redukován na polynomiální čas.
Problém univerzálnosti racionálního jazyka popsaného racionálními výrazy s umocněním
Příkladem úplného problému EXSPACE je určit, zda regulární výraz s umocněním generuje množinu slov abecedy, na které je definován. “ Pokud není umocnění v jazyce regulárního výrazu k dispozici, problém se stane úplným PSPACE. Exponentiace umožňuje, aby byly určité výrazy vyjádřeny exponenciálně výstižněji a aby bylo možné přepnout z PSPACE-Complete na EXPSPACE-Complete. Tento výsledek je podrobně demonstrován níže.
Regulární výraz s umocněním (REX)
Regulární výrazy s umocněním (REX - Regulární výrazy s umocněním ) na konečné abecedě jsou výrazy získané z písmen A následujícími operacemi:
NA{\ displaystyle A}
- Operace nebo (představuje unii)+{\ displaystyle +}∪{\ displaystyle \ cup}
- Operace (představuje produkt, bod je někdy vynechán)⋅{\ displaystyle \ cdot}
- Provoz (představuje Kleeneovu hvězdu )_⋆{\ displaystyle \ _ ^ {\ star}}
- Operace nebo (představuje umocnění řádu n)_ne{\ displaystyle \ _ ^ {n}}↑ne{\ displaystyle \ uparrow n}
Každý REX je spojen s racionálním jazykem definovaným indukčně:
E{\ displaystyle e}L(E){\ displaystyle L (e)}
-
L(∅)=∅{\ displaystyle L (\ emptyset) = \ emptyset}, L(ε)={ε}{\ displaystyle L (\ varepsilon) = \ {\ varepsilon \}}
-
L(na)={na}{\ displaystyle L (a) = \ {a \}}odkud je dopis odna{\ displaystyle a}NA{\ displaystyle A}
- L(E+F)=L(E)∪L(F){\ displaystyle L (e + f) = L (e) \ šálek L (f)}
- L(E⋅F)={X1X2:X1∈L(E),X2∈L(F)}{\ displaystyle \ L (e \ cdot f) = \ {x_ {1} x_ {2}: x_ {1} \ v L (e), x_ {2} \ v L (f) \}}
-
L(E⋆)={X1X2⋯Xk:k≥0,Xi∈L(E)}{\ displaystyle \ L (e ^ {\ star}) = \ {x_ {1} x_ {2} \ cdots x_ {k}: k \ geq 0, x_ {i} \ v L (e) \}}všimneme si také množiny možných slov v abeceděNA⋆{\ displaystyle A ^ {\ star}}NA{\ displaystyle A}
- L(Ene)={X1X2⋯Xne:Xi∈L(E)}{\ displaystyle \ L (e ^ {n}) = \ {x_ {1} x_ {2} \ cdots x_ {n}: x_ {i} \ v L (e) \}}
Máme např . Je možné nahradit jakoukoli objednávku umocňování operace by zřetězení (např je podobná ). Tato transformace však může exponenciálně zvětšit velikost vzorce. Stručnost operace umocňování přispívá k důležité prostorové složitosti níže uvedeného problému.
L((na+b)3)={nanana,nanab,nabna,nabb,⋯}{\ displaystyle L ((a + b) ^ {3}) = \ {aaa, aab, aba, abb, \ cdots \}}ne{\ displaystyle n}ne{\ displaystyle n}(na+b)3{\ displaystyle (a + b) ^ {3}}(na+b)(na+b)(na+b){\ displaystyle (a + b) (a + b) (a + b)}
Univerzální jazyk REX
Z předchozí definice REX uvažujeme následující jazyk:
NALLREX↑={E:E je REX takový L(E)=NA⋆}{\ displaystyle ALL_ {REX \ uparrow} = \ {e: e {\ text {je REX takový, že}} L (e) = A ^ {\ star} \}}
Problém tedy spočívá v určení, zda daný REX generuje množinu možných konečných slov na své abecedě (takový REX je kvalifikován jako univerzální ). Tento problém je EXPSPACE úplný:
NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}}E{\ displaystyle e}
Věta - problém je úplný EXPSPACE.
NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}}
Tato věta je stále platná, pokud omezíme umocňování na řád 2. Pokud je odstraněna Kleeneova hvězda, problém se stane NEXPTIME -kompletním.
Demonstrace
Důkaz předchozí věty se provádí ve 2 krocích. Nejprve je nutné prokázat členství v EXPSPACE, poté ukázat, že tento jazyk je EXPSPACE tvrdý (jinými slovy, jakýkoli jazyk EXPSPACE je v polynomiálním čase redukován na ).
NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}}NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}}
NALLREX↑∈{\ displaystyle ALL_ {REX \ uparrow} \ in} EXPSPACE
Vzhledem k velikosti REX umožňuje následující algoritmus v exponenciálním prostoru určit, zda :
E{\ displaystyle e}ne{\ displaystyle n}L(E)=NA⋆{\ displaystyle L (e) = A ^ {\ star}}
- Nahraďte operace umocňování zřetězeními. Dostaneme vzorec velikosti .NE=2Ó(ne){\ displaystyle N = 2 ^ {O (n)}}
- Převeďte tento vzorec (naivně) na nedeterministický automat. Tato operace vyžaduje prostor .Ó(NE){\ displaystyle O (N)}
- Určete předchozí automat. Nový řadič může mít až stavy.2Ó(NE)=22Ó(ne){\ displaystyle 2 ^ {O (N)} = 2 ^ {2 ^ {O (n)}}}
-
E{\ displaystyle e}patří tehdy a jen tehdy, když v předchozím deterministickém automatu nelze dosáhnout stavu odmítnutí. Podle Savitchovy věty to platí v prostoru na grafu velikosti .NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}}Ó(NE2){\ displaystyle O (N ^ {2})}2Ó(NE){\ displaystyle 2 ^ {O (N)}}
Protože není možné použít prostor, deterministický automat není vytvořen v kroku 3 výše. Místo toho se přepočítá při procházení krokem 4.
2Ó(NE)=22Ó(ne){\ displaystyle 2 ^ {O (N)} = 2 ^ {2 ^ {O (n)}}}
NALLREX↑{\ displaystyle ALL_ {REX \ uparrow}} je tvrdý EXPSPACE
Zvažte jazyk rozpoznaný deterministickým Turingovým strojem ve vesmíru . Budeme spojovat s REX , jako je . Přesněji, budeme mít .
L{\ displaystyle {\ mathcal {L}}} M=(Q,Γ,B,Σ,q0,δ,F){\ displaystyle M = (Q, \ Gamma, B, \ Sigma, q_ {0}, \ delta, F)}2nek{\ displaystyle 2 ^ {n ^ {k}}}w{\ displaystyle w}wR{\ displaystyle w_ {R}}w∈L⇔L(wR)∈NALLREX↑{\ displaystyle w \ in {\ mathcal {L}} \ Leftrightarrow L (w_ {R}) \ in ALL_ {REX \ uparrow}}L(wR)={s:s je slovo, které nepředstavuje odmítnutí výpočtu M Tak určitě w}{\ displaystyle L (w_ {R}) = \ {s: s {\ text {je slovo, které nepředstavuje odmítavý výpočet}} M {\ text {on}} w \}}
Stav zařízení v době jeho provedení je reprezentován slovem , kde je obsah pole pásu karet, stav zařízení a symbol umístěný pod čtecí hlavou. Protože se provádí v prostoru , můžeme předpokládat, že má velikost (i když to znamená doplnění bílými symboly ).
M{\ displaystyle M}r{\ displaystyle r}VSr=X1X2⋯XiqXi+1⋯{\ displaystyle C_ {r} = x_ {1} x_ {2} \ cdots x_ {i} qx_ {i + 1} \ cdots}Xj{\ displaystyle x_ {j}}j{\ displaystyle j}q{\ displaystyle q}Xi+1{\ displaystyle x_ {i + 1}}M{\ displaystyle M}2nek{\ displaystyle 2 ^ {n ^ {k}}}VS{\ displaystyle C}2nek{\ displaystyle 2 ^ {n ^ {k}}}B{\ displaystyle B}
Výpočet na vstupu je pak reprezentován slovem, kde každý je kódováním stavu stroje v době jeho provedení.
M{\ displaystyle M}w{\ displaystyle w}VS1#VS2#...#VSt{\ displaystyle C_ {1} \ # C_ {2} \ # \ tečky \ #C_ {t}}VSi{\ displaystyle C_ {i}}i{\ displaystyle i}
Výpočet ze na vstupu není odmítnutím, pokud splňuje alespoň jednu z následujících podmínek: 3
wVS=VS1#VS2#...#VSt{\ displaystyle w_ {C} = C_ {1} \ # C_ {2} \ # \ tečky \ #C_ {t}}M{\ displaystyle M}w{\ displaystyle w}
-
VS1{\ displaystyle C_ {1}}není možné počáteční nastavení .M{\ displaystyle M}
- existují 2 po sobě jdoucí konfigurace představující nemožný přechod.VSi,VSi+1{\ displaystyle C_ {i}, C_ {i + 1}}
-
VSt{\ displaystyle C_ {t}} není konečná odmítající konfigurace.
Pro každou z těchto 3 podmínek vytvoříme racionální výraz, který generuje množinu slov splňujících podmínku (označujeme a ).
E{\ displaystyle e}Δ=Γ∪Q∪{#}{\ displaystyle \ Delta = \ Gamma \ pohár Q \ pohár \ {\ # \}}Δ-na=Δ∖{na}{\ displaystyle \ Delta _ {- a} = \ Delta \ zpětné lomítko \ {a \}}
Podmínka 1. V počátečním okamžiku je stroj ve stavu a je zapsán na pásku. To znamená, že jediným možným počáteční konfigurace je: . Následující regulární výraz poté generuje množinu slov splňujících podmínku 1:
M{\ displaystyle M}q0{\ displaystyle q_ {0}}w{\ displaystyle w}q0w1⋯wneB⋯B{\ displaystyle q_ {0} w_ {1} \ cdots w_ {n} B \ cdots B}Rbnad-stnart=Δ-q0Δ⋆+Δ1Δ-w1Δ⋆+Δ2Δ-w2Δ⋆+⋯+Δne+1(Δ+ε)2nek-ne-2Δ-BΔ⋆+Δ2nekΔ-#Δ⋆{\ displaystyle R_ {bad-start} = \ Delta _ {- q_ {0}} \ Delta ^ {\ star} + \ Delta ^ {1} \ Delta _ {- w_ {1}} \ Delta ^ {\ star } + \ Delta ^ {2} \ Delta _ {- w_ {2}} \ Delta ^ {\ star} + \ cdots + \ Delta ^ {n + 1} (\ Delta + \ varepsilon) ^ {2 ^ {n ^ {k}} - n-2} \ Delta _ {- B} \ Delta ^ {\ star} + \ Delta ^ {2 ^ {n ^ {k}}} \ Delta _ {- \ #} \ Delta ^ {\ hvězda}}
Podmínka 2. Abychom věděli, zda je přechod platný nebo ne, postačí studovat pro každou dvojici po sobě jdoucích konfigurací okna velikosti 3 vycentrovaná na aktuální stav (například pro konfiguraci je toto okno ). Ve skutečnosti se další písmena konfigurace nemají vyvíjet po jediném kroku výpočtu. Pro dvě okna a je třeba poznamenat, zda nemohou existovat dvě po sobě jdoucí konfigurace s příslušně a pro okna. To pak generuje sadu slov kontrola na 2 za předpokladu použití následující regulární výraz: .
VS=X1X2⋯XiqXi+1⋯{\ displaystyle C = x_ {1} x_ {2} \ cdots x_ {i} qx_ {i + 1} \ cdots}XiqXi+1{\ displaystyle x_ {i} qx_ {i + 1}}nabvs.{\ displaystyle abc}dEF{\ displaystyle def}bnad(nabvs.,dEF){\ displaystyle bad (abc, def)}nabvs.{\ displaystyle abc}dEF{\ displaystyle def}Rbnad-winedÓw=⋃bnad(nabvs.,dEF)Δ⋆nabvs.Δ2nek-2dEFΔ⋆{\ displaystyle R_ {bad-window} = \ bigcup _ {bad (abc, def)} \ Delta ^ {\ star} abc \ Delta ^ {2 ^ {n ^ {k}} - 2} def \ Delta ^ { \ hvězda}}
Podmínka 3. Předpokládá se, že stroj skončí ve stavu v případě odmítnutí výpočtu. Tedy, aby se nejednalo o odmítající finální konfiguraci, stačí, že neobsahuje . Následující regulární výraz a generuje množinu slov splňujících podmínku 3 .
M{\ displaystyle M}qrEjEvs.t{\ displaystyle q_ {odmítnout}}VSt{\ displaystyle C_ {t}}wVS{\ displaystyle w_ {C}}qrEjEvs.t{\ displaystyle q_ {odmítnout}}Rbnad-rEjEvs.t=Δ-qrEjEvs.t⋆{\ displaystyle R_ {bad-reject} = \ Delta _ {- q_ {reject}} ^ {\ star}}
Nakonec si všimneme . Máme dobré a tak . Navíc se dobře staví v polynomiálním čase v ( má velikost ).
wR=Rbnad-stnart+Rbnad-winedÓw+Rbnad-rEjEvs.t{\ displaystyle w_ {R} = R_ {bad-start} + R_ {bad-window} + R_ {bad-reject}}L(wR)={s:s je slovo, které nepředstavuje odmítnutí výpočtu M Tak určitě w}{\ displaystyle L (w_ {R}) = \ {s: s {\ text {je slovo, které nepředstavuje odmítavý výpočet}} M {\ text {on}} w \}}w∈L⇔L(wR)∈NALLREX↑{\ displaystyle w \ in {\ mathcal {L}} \ Leftrightarrow L (w_ {R}) \ in ALL_ {REX \ uparrow}}wR{\ displaystyle w_ {R}}ne=|w|{\ displaystyle n = | w |}wR{\ displaystyle w_ {R}}Ó(nek){\ displaystyle O (n ^ {k})}
Logicky
Problém uspokojivosti některých fragmentů lineární časové logiky s kvantifikací prvního řádu je EXPSPACE úplný.
Bibliografie
externí odkazy
Poznámky a odkazy
-
(in) Chris Umans Kevin Lee, „ Výpočetní složitost, Poznámky k přednášce 8 “ ,19. února 2010
-
Albert R. Meyer a Larry Stockmeyer . Problém ekvivalence regulárních výrazů se čtvercem vyžaduje exponenciální prostor . 13. IEEE Symposium on Switching and Automata Theory , říjen 1972, str. 125–129.
-
I. Hodkinson , R. Kontchakov , A. Kurucz a F. Wolter , „ O výpočetní složitosti rozhodujících fragmentů lineární časové logiky prvního řádu “, 10. mezinárodní symposium o časové reprezentaci a uvažování, 2003 a čtvrtá mezinárodní konference o dočasné Logika. Sborník ,1 st 07. 2003, str. 91–98 ( DOI 10.1109 / TIME.2003.1214884 , číst online , přistupováno 17. října 2016 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">