[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/space_class_l.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "logspace" type: concept related: [Space Class L] source: https://www.jemoka.com/posts/kbhspace_class_l/ confidence: high status: active --- \begin{equation} L = \text{SPACE}\qty(\log n) \end{equation} For time, the gold standard for languages with \(\geq n\) to read input is \(\text{TIME}\qty(n)\) or at best \(\text{TIME}\qty(n^{k})\). For space, the gold standard for languages with \(\geq n\) characters is \(\text{SPACE}\qty(\log n)\), because to have pointers, store things, etc., will take this much. additional information example Here are some logspace algorithms. 0 and 1 \begin{equation} A = \qty {0^{m}1^{m}: m \in \mathbb{N}} \end{equation} palendromes We can solve it by keeping track of length of input, and then check \(x [i] = x[n-i+1]\)