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.

$$\mathrm{LSPACE}\subseteq \mathrm{P}$$

Idea

A logarithmic-space algorithm is usually described with the input stored on a separate read-only input tape. Only the work tape counts towards the space bound. This means the machine may read the input, but it can store only $\mathcal{O}(\log |I|)$ bits in its own memory. The bound is sufficient to keep a counter or a few pointers, but not enough to copy the whole input.

Examples

Find-node problem

Given a natural number $n$ and a tree $T$ whose nodes are labelled by natural numbers, the problem asks whether $T$ contains a node with label $n$.

This problem is in logspace: the input can be scanned on a separate read-only tape, while the machine stores only the current label being checked and a counter of logarithmic size. Therefore, the required workspace is $\mathcal{O}(\log |I|)$.