Space complexity

\begin{array}{r} \begin{array}{c} L = D S P A C E (\log (n)) & N L = N S P A C E (\log (n)) \\ PSPACE = ⋃_{k \geq 1} SPACE (n^{k}) & c o - N L = N L D T I M E (t (n)) \subseteq D S P A C E (t (n)) \end{array} \end{array}

STCON,PATH is NL-complete under log reductions.

NL clousre If the language $A$ is $N L$ -complete then

1. $A \in N L$ 2. Each problem in $N L$ is logspace reducible to $A$

Since $c o N L = N L$ each problem in $c o N L$ is logspace reducible to $A$ as well. Thus $A$ is $c o N L$ -complete.

Any $L \in NP$ have Log Verifier for $L$ is D-TM with 3 types $(w, c$ ,working type) $V$ run in Poly time $| x |$ and using $\log (| x |)$ types from working type. if $x \in L$ exsit $w$ s.t $V$ accept . if $x \notin L$ for all $w$ $V$ reject. $L \in N L \Leftrightarrow$ exsit Right only log time verifier.

Composition of space-bounded functions

is a bit tricky: Thm: if $f$ and $g$ are computable in space $s_{f} (n) . g_{f} (n) .$ respectively, then $g f$ is computable in space (with $m_{f}$ being a bound on the output length of $f$ ).

s_{f} (n) + \log (m_{f} (n)) + \log (m_{f} (n))