The Setting
A randomized machine that runs for steps reads one fair coin per step, and its acceptance probability on an input is an average over coin strings. The small-space way to reach it is the configuration graph. Its nodes are configurations stamped with the time, each node has one edge of weight for each coin value, and the acceptance probability is the value at the start node of the potential that collects at every accepting configuration of time . Under a polynomial clock and a logarithmic space bound the graph has polynomially many nodes, and the time stamp makes every edge go forward.
The library builds this graph for its own machine model and states that it, with its reward vector and potential, is a correct first stage of the probability hierarchy, whose stages are forward weighted graphs carrying a value vector.
Sources and Their Runs
An input is a word , read on a tape with cells that holds a left endmarker in cell , the bits of in cells to and a right endmarker in cell .
A probabilistic machine with states , with input heads and binary work tapes, consists of an initial state, an output map marking some states as accepting and some as rejecting, and a transition function.✦ From the state, the symbols under the input heads, the bits under the work heads and a coin , the transition function gives the next state, a bit to write on each work tape and a move left, stay or right for each head.✦
A configuration of on an input of length is a state together with a cell in for each input head, a position in for each work head and contents for each work tape.✦ On a coin sequence , the run of on starts from the initial configuration and makes its move at step with coin .✦ The acceptance probability of on at time is the share of coin strings of length that leave the run in an accepting state: (1)✦ The space used through time , written , is the sum over the work tapes of the number of distinct cells the tape’s head occupies at steps of that run.✦
A source is a machine with three constants , , .✦ The clock of on an input of length is .✦ A source satisfies the space bound when for every input of length , every coin sequence and every time , (2)✦
The Configuration Graph
Fix a source and an input of length with clock . A record of is a tuple of natural numbers: a time stamp , a state , a cell for each input head, and for each work tape the bits left of the head and the bits from the head rightward, as binary numbers and whose lowest digit is the cell nearest the head.✦
The step of a record with coin is the record after one move of on .✦ It raises the time stamp by one and applies the transition function to the state (read modulo ), the input symbols in the cells , the lowest digits of the and the coin ; writing replaces the lowest digit of , a work head move shifts one digit between and ✦, and the input heads stay within the cells ✦. In a state with an output, the step changes only the time stamp. The start record has time stamp , the initial state, every input head in cell and every work tape blank.✦
The radix of the input is the number (3) A record is legal for when its state is at most and each of its entries is below .✦ The node of a record is the natural number whose base- digits are , , the , the and the , the time stamp leading✦; every natural number is read back as a record through its base- digits in the same order✦. The node set of is ✦, of size polynomial in , and its start node is ✦.
For a natural number with record and a coin , the -successor of is when is legal with time stamp below and is legal; otherwise has no -successor.✦ For a vector on the natural numbers, stands for when has no -successor.✦
The transition matrix of is the matrix indexed by pairs of natural numbers with (4)✦ The reward vector of has when the record of is legal, has time stamp and has an accepting state, and otherwise.✦ The potentials of are the vectors with and (5)✦ and the potential of is ✦.
The hint of a record and a coin is the tuple (6)✦ and there are possible hints.
Prizes of the Probability Hierarchy
A stage of the probability hierarchy consists of a choice of the numerical constants that parametrize the hierarchy, a level , a finite domain and a real matrix indexed by pairs of natural numbers; its rate is ✦. A matrix is a step matrix on at rate when, for all natural numbers and , (7)✦
A prize is a stage with a weight vector and a value vector , both real vectors on the natural numbers.✦ A prize whose stage has domain , matrix and rate is correct when is a step matrix on at rate , , for every , and (8)✦
The prize of is , where is the stage at level , of rate , with domain and matrix , for a given choice of the hierarchy’s constants.✦
The Claim
Theorem 1 (Configuration reduction). Let be a source with states, input heads, work tapes and constants , , , and let be an input of length with clock . For all natural numbers and , the transition matrix of satisfies (9)✦ (10)✦ (11)✦ (12)✦ if for a coin , then (13)✦ and (14)✦ (15)✦ For records and with states at most and coins and such that and , (16)✦ For every natural number , (17)✦ and for every , (18)✦ For every choice of the hierarchy’s constants, (19)✦ If satisfies the space bound (2), then (20)✦ (21)✦ and the value vector of satisfies (22)✦
In the paper, the result reads: for a polynomial-time randomized machine using work space and an input of length , one can specify, uniformly in logarithmic space, a polynomial-size vertex set , a strictly forward substochastic matrix , a vector and a start vertex such that the incoming and outgoing port degrees of are bounded by constants depending only on the machine, port validity, edge weights and pairing are computable in logarithmic space, the vector is well-defined and lies in , and its value at is the acceptance probability, so that for a computation in randomized logarithmic space (RL) that value is or at least .
In the box, the potential after steps stands where the paper has .
What Is Checked
The claim is stated over the library’s probabilistic machines with their runs, acceptance probability and space used, over the records of a source with their steps, hints and base- numbering into the node set , over the transition matrix , the reward vector and the potentials built on them, and over the stages and prizes of the probability hierarchy with their correctness condition.