Key Sequence

New Concepts

• Space Complexity
• PSPACE
• logspace
• STCONN

Important Results / Claims

• space complexity is tricky…
• “gold standard” for space complexity is \(O\qty(\log\qty(n))\)
• \(\text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n))\)
• \(\text{SPACE} \qty(s \qty(n)) \subseteq \text{TIME}\qty(2^{O\qty(s\qty(n))})\)
• space hierarchy theorem
• Space Time Hierachy

Questions

Interesting Factoids