空間複雜度

定義2：讓 $f:N \rightarrow N$ 屬於一個function，
SPACE(f(n)) = {L | L是一組可以被O(f(n))空間的Deterministic Turing Machine所決定的language}
NSPACE(f(n)) = {L | L是一組可以被O(f(n))空間的Non-Deterministic Turing Machine所決定的language}
範例：
$SAT$屬於NP-complete，這個在NP-completeness已經證明過了，而接著要談的是$SAT$同樣可以在linear(O(m))空間內計算完成
$M_{1}$ = 輸入$<\phi>$，$\phi$是Boolean formula

對於每一個真值參數給$\phi$的變數$x_{1},….,x_{m}$
使用剛才拿到的true或false計算$\phi$
如果$\phi$輸出1，代表ACCEPT，反之輸出REJECT

讓$E_{NFA} = \{ <A>$| A是一個NFA(Non-deterministic Finite Automata)並且L(A) = $\phi \}$
範例: $E_{NFA}$可以在Non-deterministic linear space決定輸出
N = 輸入一組NFA的$<M>$

放一個標記(marker)在NFA的start state
重複執行$2^{q}$次，$q$是M的state數量
Nondeterministically選擇一個輸入符號以及改變標記(marker)M的狀態位置，模擬讀進來一個符號
如果標記(marker)已經有放進去過輸入狀態就REJECT，反之ACCEPT

Savitch’s Theorem

對於任何的function $f: N \rightarrow N$，其中$f(n) \geq n$
$$NSPACE(f(n)) \subseteq SPACE(f^{2}(n))$$
證明：
N: 是一個non-deterministic Turing Machine可以決定一個language A在space f(n)
目標：建構一個deterministic Turing Machine M來決定language A在$SPACE(f^{2}(n))$
存在一個$\omega$作為N的輸入
$t$: 整數，$c_{1}, c_{2}$是$N$輸入$\omega$的configurations
$CANYIELD(c_{1}, c_{2}, t)$如果從$c_{1}$的configuration作為起始N就存在一條路徑可以走到$c_{2}$在$t$個步驟之後，就輸出accept，反之輸出rejects
$CANYIELD$ = 輸入$c_{1}, c_{2}, t$

如果$t=1$，測試$c_{1}$是否等於$c_{2}$，或者$c_{1} \vdash c_{2}$，則輸出accept，反之輸出reject
如果$t > 1$，則對於每一個configuration $c_{m}$在$N$輸入$\omega$都是在space $f(n)$完成
執行$CANYIELD(c_{1}, c_{m}, \lceil \frac{t}{2} \rceil)$
執行$CANYIELD(c_{m}, c_{2}, \lceil \frac{t}{2} \rceil)$
如果3跟4的步驟執行完可以完成就輸出accept，反之輸出reject

$C_{accept}$: accept configuration
$C_{start}$: start configuration在N輸入$\omega$
選擇一個常數$d$使得N沒辦法執行超過$2^{df(n)}$的configuration在使用$f(n)$的tape空間下，$n = |\omega|$
M = 輸入$\omega$
輸出$CANYIELD(C_{start}, C_{accept}, 2^{df(n)})$的結果
$CANYIELD$是一個遞迴的執行過程

遞迴深度：$log_{2}2^{df(n)} = O(f(n))$
每一次呼叫遞迴的$CANYIELD$都使用$O(f(n))$的空間當作stack
因此在使用了上限是$O(f(n))$的configuration以及$O(f(n))$的stack總共使用了$O(f^{2}(n))$的空間

PSPACE同樣可以是作為一個language(或是問題)的class，在這space的限制下deterministic Turing Machine可以在多項式空間下決定輸出
$$PSPACE = \bigcup_{k} SPACE(n^{k})$$
定理：$$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME = \bigcup_{k}TIME(2^{n^{k}})$$
定義：(PSPACE completeness)
一個language(或是問題(Probmel)) B如果滿足兩個條件則屬於PSPACE-complete：

B在PSPACE並且
任何屬於PSPACE的language A(或Problem)可以在多項式時間內轉換到問題B

$\forall$: universal quantifier, $\forall x > [x+1 > x]$
$\exists$: existential quantifier, $\exists y > [y+y = 3]$
$\forall x \exists y > [y > x]$是存在的
$\exists y \forall x > [y > x]$是不存在的
$\phi = \forall x \exists y > [(x \vee y) \wedge (\bar{x} \vee \bar{y})]$通常稱作quantified Boolean formula或是fully quantified Boolean formula

TQBF

TQBF：給定一組fully quantified Boolean formula，輸出是否為true?
定理：TQBF屬於PSPACE-complete
證明：TQBF屬於PSPACE:
T = 輸入$\phi$，$\phi$是一組fully quantified Boolean formula:

如果$\phi$沒有quantifier，那就只是一組常數組成的運算式，計算完$\phi$之後如果一樣輸出true代表輸出accept，反之輸出reject跟前面提到的boolean formula一樣
如果$\phi = \exists x \Psi$，遞迴呼叫T輸入$\Psi$，首先$x = 0$ 接著$x = 1$，如果輸出是accept就accept反之reject
如果$\phi = \forall x \Psi$，遞迴呼叫T輸入$\Psi$以及$x = 0, x = 1$，如果兩個輸入結果都是accept，就輸出accept，反之reject

TQBF屬於PSPACE-hard:
存在一組language A可以被Turing Machine M在SPACE $n^{k}$所決定結果，$k \in$ 常數
證明: $A \leq_{p} TQBF$
如果$\phi$輸出是true代表M接受$\omega$
$c_{1}, c_{2}$: configurations
t: 整數；$\phi_{C_{1},C_{2},t}$: 是一個formula
$\phi = \phi_{C_{start}, C_{accept}, h}, h = 2^{df(n)}$
$\phi_{C_{1}, C_{2}, t} = \exists m_{1}, \forall(C_{3},C_{4}) \in {(C_{1},m_{1}), (m_{1}, C_{2})}[\phi_{C_{3},C_{4}, \lceil \frac{t}{2} \rceil}]$
Configuration大小：$O(f(n))$
遞迴深度：$log_{2} 2^{df(n)} = O(f(n))$
Formula大小：$O(f^{2}(n))$
以上的方法是多取兩個configuration當做暫定的變數，可以先算好一半，再去算另一半的遞迴所以才讓space可以壓在$O(f^{2}(n))$之內，如果不存在$C_{3}, C_{4}$的話？
$\phi_{C_{1}, C_{2}, t} = \exists m, [\phi_{C_{1}, m, \lceil \frac{t}{2} \rceil} \wedge \phi_{m, C_{2}, \lceil \frac{t}{2} \rceil}]$會變成需要多少空間？

Winning Strategies for games:

$$\phi = \exists x_{1} \forall x_{2} \exists x_{3} … Q_{x_{k}}[\Psi]$$
$Q$可以表示成$\forall$或是$\exists$的quantifier
存在兩個player: player $A$以及player $E$
每一次的遞迴都選擇不同的值給$x_{1}, …, x_{k}$

Player A選擇值給$\forall$的變數
Player E選擇值給$\exists$的變數
如果$\Psi$輸出TRUE，代表player $E$贏了
如果$\Psi$輸出FALSE，代表player $A$贏了

範例：
存在$$\phi_{1} = \exists x_{1} \forall x_{2} \exists x_{3}[(x_{1} \vee x_{2}) \wedge (x_{2} \vee x_{3}) \wedge (\bar{x_{2}} \vee \bar{x_{3}})]$$
player $E$存在一組可以贏的策略
$$x_{1} = 1, \begin{cases} x_{2}=0, x_{3}=1 \ x_{2} = 1, x_{3} = 0 \end{cases} \Rightarrow \phi_{1} = TRUE$$
存在$$\phi_{2} = \exists x_{1} \forall x_{2} \exists x_{3}[(x_{1} \vee x_{2}) \wedge (x_{2} \vee x_{3}) \wedge (x_{2} \vee \bar{x_{3}})]$$
player $A$存在一組可以贏的策略
$$x_{1} = 0, \begin{cases} x_{2}=0, x_{3}=1 \ x_{2} = 1, x_{3} = 0 \end{cases} \Rightarrow \phi_{2} = FALSE$$
FORMULA-GAME = $\{<\phi>$|player E在formula-game中擁有獲勝的策略滿足[latex]\phi$}
定理：FORMULA-GAME屬於PSPACE-complete
證明：
$\phi \in TQBF$當$\phi \in FORMULA-GAME$
假設一個問題存在兩個player A以及player E看著同一張地圖，player A先選一個城市，下一手player E必須選擇player A選定城市的字母結尾當作開頭的城市，途中每一手不能挑已經選過的城市，重複直到其中一個player沒有城市可以選擇，選不出來的就算輸。

將這種問題稱作Geography Game(GG):

player 1選擇第一動，接著才換player 2動，player 1要能夠贏的策略：
起始從1開始，
player 1選擇3，
player 2選擇5，
player 1選擇6，
player 2沒辦法選出下一手，因為3已經走過了，
所以player 1獲勝

Geography Game = $\{<G, b>$ | player 1在generalized geography game圖$G$起始點$b$開始擁有獲勝的策略}
定理：Geography Game屬於PSPACE-complete
證明：
M = 輸入$<G, b>$，$G$為有向圖，$b:G$裡的一個點

0. 如果起始點$b$沒有路徑出去就reject

刪除點$b$並且剩餘的nodes形成新的graph $G_{1}$
$b$原本所指向每一個node $b_{1},b_{2}, …, b_{k}$，都當作新的$b$去呼叫$<G, b_{i}>$
如果全部呼叫的結果最後都accept，代表player 2贏了這次的game，所以輸出REJECT，反之如果player 2沒辦法贏這個game，代表獲勝的是player 1並且輸出ACCEPT

需要的空間是每一次重新產生的graph的大小所以是遞迴的stack大小即可
而stack的level最多只需要$m$個，是當次graph $G$的node數量
每一level只需要polynomial空間，因此整個M也只需要polynomial空間
接下來證明Geography Game是PSPACE-hard:
$FORMULA-GAME \leq_{p} Geography \> Game$
$$\phi = \exists x_{1} \forall x_{2} \exists x_{3}…Q_{x_{k}} \Psi \leq_{p} <G, b>$$
Geography Game player 1 $\thicksim$ formula game player E
Geography Game player 2 $\thicksim$ formula game player A
$$\phi = \exists x_{1} \forall x_{2}….Q_{x_{k}}[(x_{1} \vee x_{2} \vee x_{3}) \wedge (x_{2} \vee x_{3} \vee …)\wedge … \wedge (…)]$$
為了方便好說明，先假設$Q = \exists$

如果$\phi$輸出FALSE，代表player 2選擇到了未滿足的clause可能獲勝，player 1可能選擇FALSE的node，該node連接左邊還沒選擇過的路徑，因此player 2可能會去選左邊其中一個node，而player 1就沒辦法選下一個node導致輸掉
如果$\phi$輸出TRUE，代表player 2選擇的clause裡面包含TURE的literal，如果player 1選擇TRUE literal
$\because$該node是true，$\therefore$該node連接左邊的node是已經被選過的，讓player 2再下一步沒得選而輸掉

L以及NL類型

$L = SPACE(log \> n)$
$NL = NSPACE (log \> n)$
範例：$PATH = \{<G, s, t>$| $G$是一個有向圖存在有向路徑從$s$到$t$}
$PATH$: 給訂一個有向圖$G$以及兩個頂點$s$以及$t$，是否存在一條有向路徑從$s$可以走到$t$?
定義：如果$M$是一個Turing Machine

$M$輸入$\omega$的一組configuration內容包括設定的狀態、tape內容，以及tape讀寫頭的位置
如果$M$在輸入$\omega$的執行空間在$f(n)$，$|\omega| = n$，則$M$輸入$\omega$的configuration數量就會有：
$$g^{f(n)} \times f(n) \times c \times n \approx 2^{O(f(n))}$$
$g:$tape裡面符號的數量
$c:$所有可能的狀態數量
$g^{f(n)}:$所有可能的tape內容數量
$f(n):$狀態可能的位置
$n:$輸入讀寫頭可能的位置空間

Savitch’s theorem對於$f(n) \geq log\>n$會輸出true

NL-completeness: NL $\underset{=}{?}$ L

定義：(log space reducibility)

一個log space轉換透過Turing Machine使用
- read-only輸入tape
- write-only輸出tape
- 讀/寫work tape(可能包含$O(log \> n)$個符號)
一個log space轉換$M$計算function $f: \Sigma^{*} \rightarrow \Sigma^{*}$，其中$f(n)$是M在輸入tape放進$\omega$所停止的輸出字串，$f$可以稱作log space computable function
$A \leq_{L} B$，如果問題$A$可以在log space computable function映射轉換到問題$B$

定義：一個language B屬於NL-complete如果

$B \in NL$並且
任何問題A可以在log space之內轉換到問題B

定理：如果$A \leq_{L} B$並且$B \in L$則$A \in L$
推論(cor)：如果任何NL-complete語言在L裡代表$L = NL$
定理：$PATH$屬於NL-complete
證明：
證明$A \in NL, A \leq_{L} PATH$
存在一組Non-deterministic Turing Machine M可以在$O(log \> n)$的空間決定A
給一組輸入$\omega$，建構一個graph $G$以及兩個頂點$s$跟$t$在log space，如果$M$可以accept $\omega$則代表graph $G$存在一條有向path可以從$s$抵達$t$
$V(G):$ M輸入$\omega$的configuration
$(C_{1}, C_{2}) \in E(G) \> if \> C_{1} \vdash C_{2}$
$s:$ start configuration, $t:$ accept configuration

需要證明轉換的操作可以在log space內完成，換言之需要描述$G$的頂點以及邊最多可以用log space儲存
每一個configuration需要$c \> log \>n$的空間，$c$是常數
嘗試所有可能的$c \> log \> n$長度的字串給輸入$\omega$的M來看是不是合法的configuration，如果是的話就將那組string放進頂點集合內
對於任何(需要$O(log\>n)$的空間)的$C_{1}, C_{2}$測試$M$輸入$\omega$看看存不存在$C_{1} \vdash C_{2}$
推論(Cor)：$NL \subseteq P$
$PATH \in P \Rightarrow NL \subseteq P$
推論(Cor)：$co-NL = \{B: \overline{B}$屬於NL}

定理：NL = co-NL
證明：
$PATH$屬於NL-complete $\Rightarrow \overline{PATH} \in$ co-NL
如果$ \in \overline{PATH}$的話，代表不存在任何有向路徑在graph $G$內可以從$s$走到$t$
對於任何的$A \in$ co-NL 是 $A \leq_{L} \overline{PATH}$
這就代表$\overline{PATH} \in NL$

Scientia Potentia Est

Scientia Potentia Est

空間複雜度

目錄

Savitch’s Theorem

TQBF

Winning Strategies for games:

L以及NL類型

NL-completeness: NL \(\underset{=}{?}\) L

Scientia

Related Posts

NP-completeness

時間複雜度

發佈留言取消回覆

Other Story

空間複雜度

NP-completeness

時間複雜度

不同的Turing Machine

Turing Machine

熵 Entropy

Scientia Potentia Est

Scientia Potentia Est

空間複雜度

空間複雜度

目錄

Savitch’s Theorem

TQBF

Winning Strategies for games:

L以及NL類型

NL-completeness: NL \(\underset{=}{?}\) L

Scientia

Related Posts

NP-completeness

時間複雜度

發佈留言 取消回覆

Other Story

空間複雜度

NP-completeness

時間複雜度

不同的Turing Machine

Turing Machine

熵 Entropy

發佈留言取消回覆