0

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?

Erick Wong
  • 25,198
  • 3
  • 37
  • 91
Benny
  • 29
  • Saavitch’s theorem shows that any problem that’s already in NSPACE($\log n$) also belongs to DSPACE($\log^2 n$). It does not help you to show that a specific problem belongs to NSPACE. – Erick Wong Apr 15 '21 at 17:12
  • can you please briefly and simply explain this proof – Benny Apr 15 '21 at 17:16
  • What don’t you understand about https://en.m.wikipedia.org/wiki/St-connectivity ? – Erick Wong Apr 15 '21 at 17:17

1 Answers1

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.

ml0105
  • 14,674
  • We need to store additionally $\lceil \log(|V|) \rceil$ bits to store the number of steps we have made. Otherwise we can potentially get stuck in a loop. – ark Nov 08 '23 at 11:49