Space complexity

\[ \begin{aligned} \begin{matrix} L=DSPACE(\log (n)) & \quad & NL = NSPACE(\log (n)) \\ \mathrm{PSPACE}= \bigcup _{k\geq 1} \mathrm{SPACE}(n^k) & \quad & co-NL=NL\qquad DTIME(t(n))\subseteq DSPACE(t(n)) \end{matrix}\\ \end{aligned} \]

STCON,PATH is NL-complete under log reductions.

NL clousre If the language \(A\) is \(NL\)-complete then

1. \(A \in NL\) 2. Each problem in \(NL\) is logspace reducible to \(A\)

Since \(coNL = NL\) each problem in \(coNL\) is logspace reducible to \(A\) as well. Thus \(A\) is \(coNL\)-complete.

Any \(L\in \mathcal{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 NL \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)) \]