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.
