Key Sequence New Concepts Space Complexity PSPACE logspace STCONN Important Results / Claims space complexity is tricky… “gold standard” for space complexity is O\left(\log\left(n\right)\right) \text{TIME}\left(t\left(n\right)\right) \subseteq \text{SPACE}\left(t\left(n\right)\right) \text{SPACE} \left(s \left(n\right)\right) \subseteq \text{TIME}\left(2^{O\left(s\left(n\right)\right)}\right) space hierarchy theorem Space Time Hierachy Questions Interesting Factoids