Logspace Complexity Class

complexity-theory

Definition

Logspace Complexity Class

The logspace complexity class contains all decision problems solvable by a deterministic Turing machine using logarithmic space on the work tape (input tape is read-only).

• Space usage: $\mathcal{O}(\log |I|)$

The logspace complexity class is a subset of the polynomial complexity class.