Logarithmic space is a bound of 
bits of working memory for a computation
on an input of length 
.
A read-only input tape and a write-only output tape are excluded from working memory.
The class 
consists of decision problems decidable by a
halting deterministic Turing machine with this
bound. Such a machine has only polynomially many configurations, so its running time
is polynomial.
The classes 
and 
use fresh independent fair random bits, the same space bound, and polynomial
running time on every random tape. For 
, no-instances have acceptance probability
zero and yes-instances at least 
. For 
, those probabilities are
at most 
and at least 
,
respectively.
