The Setting
Take a probabilistic Turing machine that works in logarithmic space within a polynomial clock, and a language that recognizes with bounded error: it accepts each word of with probability at least and each other word with probability at most . Placing in means telling the two cases apart by a deterministic machine in logarithmic space, here by estimating the acceptance probability and comparing the estimate with .
The estimate is built from sampling environments, triples of affine lines in for a prime : a logspace computable function is evaluated on each of them and averaged. The question is how close that function has to come to the estimator of the acceptance probability, a real-valued function of an environment computed on the configuration graph of on the input, for the average to separate from , and how the comparison with stays within logarithmic space.
Machines, Clocks and Configurations
A probabilistic Turing machine with states , binary work tapes and input heads has an initial state, an output at each state (accept, reject or none, the states with an output being the halting ones) and a transition.✦ The transition maps a state, the input symbols under the input heads, the bits under the work heads and a coin bit to a next state, a bit to write on each work tape and a move, left, stay or right, of every head. The input tape holds the word , of length , between a left and a right endmarker.✦ The run on with an infinite coin tape starts in the initial configuration and takes its step at time with the coin ✦; the space it uses through time is the number of distinct cells its work heads have visited by then, summed over the work tapes.✦
A source machine is a probabilistic Turing machine together with a space coefficient and a clock with constants and .✦ A source machine keeps its space bound when on every input , with every coin tape and through every time, it uses at most cells.✦ The acceptance probability of a source machine on an input is the fraction of the coin sequences of length on which the run of on is in an accepting state at time : (1)✦
A language is a set of binary words.✦ A machine is deterministic when its transition ignores the coin bit✦; it runs in logarithmic space when for some it uses at most cells on every input, coin tape and time✦; and it decides a language when for every input there is a time at which, whatever the coins, its state has the output accept if and reject otherwise.✦ The class is the set of languages decided by a deterministic machine that runs in logarithmic space.✦
The configuration graph of a source machine on an input has the numbered configurations of on as its nodes. A register record lists a time, a state, the positions of the input heads, and each work tape as two numbers whose binary digits are the cells left of the head and the cells from the head rightward.✦ The node of a register record is the number whose digits in the node radix are the registers of the record, and the nodes are the numbers below the node count . A record is legal when its registers are below and its state number is at most .✦ The initial node is the node of the start record: time , the initial state, every input head on cell and blank work tapes.✦ From a node with a legal record of time below , the coin leads to the node of the record after one step, when that record is legal.✦ The halved edge weight is half the number of coins that lead from to ✦, and is an accepting final node when its record is legal, has time and an accepting state.✦ A step of a record increases the time by one, replaces the state by the next state given by the transition, overwrites the cell under each work head and moves that head, and moves each input head in the direction the transition gives, an input head staying on the cells to . When the state has an output, a step changes nothing: the state is kept, the scanned bits are rewritten unchanged and every head stays in place.
Environments and the Evidence
The analytic constants of a source machine are an iteration count of the estimator that is admissible, a number of copies of each vertex, the copies of being for , two sizes and with and , where and is the cutoff scale, and two natural numbers and . An admissibility certificate for the analytic constants consists of a constant that bounds the fourth roots of the cutoff profiles of the estimator and their Lipschitz constants, budget constants that meet the credit condition at , and the walk length condition , where with the gap constant , , and the set of generator choices of the random walk of length that the estimator uses.✦ The bank of an admissibility certificate is , with the width .✦
Fix a source machine with analytic constants, an input , a natural number , the budget, and a prime . A channel over is a pair of a nonzero direction and an offset ✦; its point at is , so that it describes an affine line.✦ An environment is a triple of channels.✦ The box of level is the set of vectors of whose four coordinates have least nonnegative representatives below .✦
The start vertex is , read in : the copy of index of the initial node, taken times. An environment retains the start when its first line passes through the box of level at the start vertex, (2)✦ and is the set of environments that retain the start.
The evidence of a real function on environments is its average over the environments whose first channel has a nonzero direction and passes through a point of at : (3)✦
For the budget and the prime , the estimator is a real-valued function of an environment and a vertex, computed on the configuration graph of on : the nodes below , weighted by the halved edge weights , with reward at the accepting final nodes and elsewhere. denotes its value on the environment at the start vertex .
A source machine with analytic constants, an input , a budget and a prime are ready for an admissibility certificate with bank when (4)✦ where the ceiling is an affine function of .
The Threshold Test
With the bit length of a positive integer and a padding , the bit budget of is (5)✦ and the field size is the largest prime with , where .✦ denotes the value of the estimator on an environment over at the start vertex, for the budget and the prime . An environment over has the code , the natural number that lists, in a fixed encoding of tuples, the coordinates of the directions and offsets of its three channels as numbers below .✦
A counter program works on registers that hold natural numbers: it moves a register up or down by one, and it branches or loops on the input symbol in the cell a register points to.✦ An expression of a counter program is what the program writes into a register; a map from a word and a natural number to a natural number is logspace-computable when, for some exponent and read on codes, it carries every such expression, with its registers kept below whenever they start below some , to an expression of the same kind.✦ The survey value of such an on an environment over is the dyadic number (6)✦
A natural number qualifies at when it is the code of a triple of channels, with coordinates below and nonzero directions, whose first channel passes the retention test in integers: every coordinate of is below .✦ Over the qualifying below , one more than the code of the triple whose coordinates all equal , the census counts them✦ and the capped sum of adds their capped values: (7)✦ The threshold answer of at is (8)✦
The Claim
Theorem 1 (Fixed inverse-polynomial accuracy). (a) Let be a source machine with analytic constants, an input, a budget and a prime. For every real function on environments, (9)✦
(b) Suppose moreover that keeps its space bound, that the data are ready for an admissibility certificate of the constants, and that is a real function on environments with for every environment that retains the start. Then (10)✦
(c) Let and be reals with , let and be natural numbers with , and let be a statement such that if holds and if it fails. Then (11)✦
(d) Let be a language and a source machine that keeps its space bound, whose analytic constants carry an admissibility certificate with bank for a padding . Let be a logspace computable map with for every input and every environment over that retains the start. If for every and for every , then (12)✦
In the paper, the result reads: for a randomized machine with polynomial worst-case running time and work space and an integer , there is a uniform deterministic transducer that outputs a dyadic with , in work space and output length and polynomial time, with constants depending on and only.
What Is Checked
The claims (9), (10), (11) and (12) are stated over the library’s probabilistic Turing machines, with their acceptance probability (1) within a polynomial clock, their space bound and the class ; over the configuration graph and the bit budget (5); over the environments of three channels over , the retention test (2), the evidence (3), the readiness conditions (4) and the estimator’s value ; and over the survey values (6), the census and capped sums (7) and the threshold answer (8).