202402091102

Savitch’s Theorem

Theorem: $S (n) \geq lo g n$ is fully space constructible then $NSP A CE (S (n))$ is contained in $D SP A CE (S (n)^{2})$ .

Proof: Let $M$ be an $NSP A CE (S (n))$ Turing machine.

Goal: To construct a $D TM$ $M^{'}$ s.t. $M^{'}$ is $S (n)^{2}$ space bounded and $L (M) = L (M^{'})$ . Intuitive idea: Let $w \in {0, 1}^{n}$ be a length $n$ input for $M$ . Configurations for $M$ are of the form: (Instantaneous Description) (head position on input tape, Contents of worktape) size $= O (lo g n + S (n)) = O (S (n))$ $I_{0} :$ initial configuration $I_{f} :$ (wlog unique) accepting configuration

Configuration graph $G = (V, E)$ $V :$ set of all configurations, $∣ V ∣ \leq c^{S (n)}$ $E :$ $I_{1} \mapsto I_{2}$ then $(I_{1}, I_{2}) \in E$ $M^{'}$ is going to check if there is a directed path from $I_{0}$ to $I_{f}$ in $G$ in space $O (S (n)^{2})$ .

$RE A C H (I_{1}, I_{2}, i)$ is true if there is a directed path from $I_{1}$ to $I_{2}$ of length $\leq 2^{i}$ .

$RE A C H (I_{0}, I_{f}, S (n) lo g c)$

$RE A C H (I_{1}, I_{2}, i)$ if $i = 0$ then if $I_{1} = I_{2}$ or if $I_{1} \mapsto I_{2}$ , then true; for each $I^{'} \in V$ , do if $RE A C H (I_{1}, I^{'}, i - 1)$ and $RE A C H (I^{'}, I_{2}, i - 1)$ , then true;

Remark:

Basically undirected graph reachability has an $O (lo g n)^{2}$ space algorithm.

Reingold, 2004:

For undirected graphs, reachability can be solved in $O (lo g n)$ space.

$N L = NSP A CE (lo g n)$ $L = D SP A CE (lo g n)$ Savitch $⟹ N L \subseteq D SP A CE (lo g^{2} n)$ $L \subseteq N L \subseteq P$ $N L = co N L$ $NSP A CE (S (n)) = co NSP A CE (S (n))$ $NSP A CE (n) = CS L$ (Context Sensitive Language) $2 - S A T$ is $N L -$ complete under logspace computable reductions

🏠 No Place Like ~

Explorer

Savitch’s Theorem

References

Graph View

Table of Contents

Backlinks