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:

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

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 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 and a tree whose nodes are labelled by natural numbers, the problem asks whether contains a node with label .

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 .