The Setting
The classes (deterministic logarithmic space), (randomized logarithmic space) and (bounded-error probabilistic logarithmic space) collect the languages decidable with logarithmically many bits of working memory, deterministically, with one-sided error and with two-sided error respectively. Stated exactly, each depends on the conventions of the machine model: how the input is delimited, how coins are read, what counts as a cell of space, when a run must stop and at which time the acceptance probability is taken. The library fixes these conventions in one concrete model and defines the three classes over it.
Words, Inputs and Machines
A binary word of length is a finite sequence of bits, (1)✦ and a language is a set of binary words, (2)✦
The input tape holds between a left endmarker and a right endmarker : its cells carry ✦, so an input head reads a symbol of .✦ A head moves in a direction of (left, stay, right).✦ A machine reads the input with input heads and has work tapes, each indexed by and scanned by a work head that moves freely on ; an input head that would leave the cells stays where it is.✦
A machine with states , work tapes and input heads consists of an initial state , an output map and a transition function (3)✦ States with output are accepting and states with output are rejecting; together they are the halting states, and the states with output are not halting.
Configurations and Runs
A configuration of on inputs of length is a quadruple (4)✦ of a state, the cells of the input heads, the cells of the work heads and the contents of the work tapes, one bit in every cell of . Its state is written , and the cell of work head is written .
The step of on input with coin bit is the map on configurations that fixes every configuration in a halting state and sends any other to (5)✦ Here are the symbols under the input heads, are the bits under the work heads, is with the bit written in cell of work tape , and the input heads move by under the endmarker rule.
A coin tape is an infinite sequence of bits .✦ The initial configuration of on inputs of length is the configuration in the initial state with every input head and every work head at its starting cell and the work tapes in their starting contents. The run of on a word with coin tape is the sequence of configurations that starts at of on inputs of length and spends the coin on the step from time to time : (6)✦
Space, Time and Acceptance
The space used by on with coin tape through time is the number of distinct cells its work heads visit up to time , counted tape by tape: (7)✦
A machine runs in logarithmic space when there is an integer such that for every word , coin tape and time (8)✦
The machine is deterministic when its transition function ignores the coin bit: (9)✦
On a word , the machine halts by time when its run is in a halting state at time whatever the coins: (10)✦
The machine decides a language when on every word there is a time at which, whatever the coins, it has halted with the right answer: (11)✦ where is for and for .
The acceptance probability of on at time is the fraction of coin strings whose run, on the coin tape followed by zeros, is in an accepting state at time : (12)✦
The polynomial clock with constants is the time bound on inputs of length (13)✦
The Definition
Definition 1. The class is the set of languages (14)✦ A language is in when there are a machine running in logarithmic space and integers and such that, on every word of length , halts by time and (15)✦ A language is in when the same holds with the acceptance condition replaced by (16)✦
In the paper, the definitions read: a machine has a finite control, an endmarked read-only input, finitely many work tapes and fresh fair coin bits, and its space counts the work cells it traverses; consists of the languages decided by deterministic machines in space , of those decided by randomized machines running in polynomial time in this space with acceptance probability on inputs outside the language and at least on inputs in it, and of those decided by the same machines with acceptance probability at most on inputs outside the language and at least on inputs in it.
What Is Checked
The classes (14), (15) and (16) are stated over binary words (1) and languages (2), the machine (3) with its configurations (4), steps (5) and runs (6), and the notions built on it: the space used (7), running in logarithmic space (8), determinism (9), halting by a time (10), deciding a language (11), the acceptance probability (12) and the polynomial clock (13).