Key Sequence

Notation

New Concepts

• STCONN
  • Savitch’s Algorithm
  • PATH
• NL and Non-Deterministic Space
  • problems in \(NL\)
  • \(NL \subseteq P\)
  • \(NL \subseteq \text{SPACE}\qty(\log^{2}\qty(n))\)
  • \(\text{NL} = \text{coNL}\)

Important Results / Claims

• STCONN is in NL

Questions

Interesting Factoids