Sketch a proof that stCONN is in the class NSPACE(log n) = NL .

Question

Given a graph G as input stCONN is the problem of determining if there is a path from start vertex s to target vertex t. Sketch a proof that stCONN is in the class NSPACE(log n) = NL.

Can somebody please explain this to me as simply as possible? I don't know if I understand the problem correctly, wouldn't Savitch's theorem be enough to prove this?

Answer 1

Let $G$ be our input graph, and let $s, t \in V(G)$ be our vertices. We may guess an $s \to t$ path, one vertex at a time.

Precisely, we do the following:

• Let $\textsf{current} := s$.
• While $\textsf{current} \neq t$:
  • Guess a vertex $v$ and check that $(\textsf{current}, v) \in E(G)$. If so, set $\text{current} := v$.

We are only storing two vertices at any point in time. Each vertex requires $\lceil \log(|V|) \rceil$ bits to specify, so we are using $O(\log(n))$ space.