The Setting
Let be a randomized machine running in logarithmic space and an input of length . The analytic estimator of on is a real-valued function of a sampling environment, a triple of lines in a four-dimensional space over a prime field; it is built from the configuration graph of on by a recursion over rounds, driven by a controller program defined below, in which the table answering each request of the controller is assembled from the tables of earlier rounds. A deterministic machine with work space has no room for an unbounded call stack: each pending call may save only a short frame, and the frames saved along a chain of nested calls must fit in the bits that a meter, a function assigning a number of bits to each level, grants at the outermost level. The question is whether a recursive program run under such a budget, and in particular the estimator’s controller with suitable parameters, is carried out by one logspace function, and how close that function comes to the estimator’s value at the start.
Logspace Functions and Controller Programs
A counter program reads an input word of length and acts on registers holding natural numbers. A counter program is built from single steps that increase, decrease or keep one register, from sequencing, and from branches and while loops whose test is a property of the input symbol in the cell whose index a register holds.✦ A numeric function of the input and the registers is register computable when it depends on finitely many registers and, for every register and every large enough , some counter program with an exponent overwrites by whenever it starts from registers below some that vanish from index on, keeping every register below throughout and leaving the registers from index on at zero.✦ With arguments and values coded by natural numbers, a function of an input word and an argument is logspace computable when, for every register computable , the function (1)✦ is register computable, where is the argument with code and is the code of a value.
A controller program acts, for an input word and at a level , on states , pairs of natural numbers made of a frame and a shared value ; one controller program is fixed as the main program, the target of every call. Controller programs are built from edit steps, which replace by ; calls, which compute a callee level , run at level from the state to a state and replace by ; sequencing; branches on a flag ; and while loops on such a flag.✦ The maps , , and the flags are logspace computable.
Under a budget , a limit together with a meter , a state is admissible at level when the first three inequalities below hold, and a call from level with frame to level is affordable when the last one holds: (2) where is the bit length, with . A stack certificate that a controller program takes to at level , for the input , the budget and the main program , is a finite derivation of that run by the rules of the constructs, in which every edit step and every call starts and ends in states admissible at level , every loop exits from an admissible state, and every call is affordable and rests on a stack certificate that takes to the returned state at the callee level.✦
Instances and the Estimator
An instance consists of a source machine , analytic constants and a padding .✦ The source machine is a probabilistic Turing machine with binary work tapes and input heads, given with a space coefficient and a polynomial clock ✦; it keeps its space bound when, on every input , with every coin tape and through every time, the work cells it has visited, summed over its tapes, number at most .✦ The analytic constants are a precision , a walk length and parameter constants ✦: an iteration count with , indices and with and , and a number of copies of each vertex, where , and .✦
The estimator’s recursion uses three ramps, called boost, cutoff and shutoff, and a profile for every request kind. The analytic constants are admissible with a constant when the fourth roots of the three ramps are -Lipschitz, and every request kind has profiles, each a triple of a start figure, a row figure and a quotient figure, all nonnegative, constant on each ray outside , with fourth roots at most and -Lipschitz, where for the threshold of the kind, equal to for a chip or a slot, to for an echo and to for a score, the start figure vanishes for , the row figure vanishes for and equals for ; when there are real budgets, a ceiling, a slip and a toll, with a derived prize and venture, meeting the prescribed inequalities, such that the prize, the venture and times the squared toll are each at most , where the bank is (3)✦ and when for the loss of the walk on the set of generator choices, with the gap constant and .
For an input of length , the instance fixes the bit budget and the top round , (4) where is the number of nodes of the configuration graph of on ; with the roof , the field size is the largest prime in for .✦
A sampling environment over is a triple of rank channels, each a pair of a nonzero direction and an offset in describing the line .✦ Its code codes the coordinates of the three channels as natural numbers below .
The analytic estimator of on is the forecast of a scene built from , which assigns to every request of the controller, round by round, a table over sampling environments and vertices. The scene has height , levels, roof , gap and walk length , and starts from the prize of on ✦: the stage at level whose domain is the set of nodes of the configuration graph and whose matrix gives, for nodes and , the probability that one coin leads from to , together with the accepting rewards and the acceptance potentials of the nodes.✦ The forecast at round gives every request of the controller a table over sampling environments and vertices: a request active at that round receives its table built from the forecasts of the earlier rounds, and an inactive one the zero table.✦ The estimator’s value at the start, , is the entry at of the table of the prize request at level , taken at the vertex , the copy at depth of the initial node of on .
The estimator’s contract relates the instance to precision parameters , to controller tags , among them an exponent , a constant , a slope , a clock offset and a bonus , which give the controller the clock on , and to a natural number . The contract holds when the analytic constants are admissible with a constant satisfying and ; when , is at least plus the reserve of the analytic constants, and ; when and for the boot cost of the instance; when is at least , , and the bit length of the capacity constant, and ; and when is at least , , , for and for , and the cost bound of each component program of the estimator; here the reserve, the boot cost, the capacity constant and the cost bounds are quantities determined by the instance and the estimator.✦
The Claim
Theorem 1. Let be a controller program. There is a logspace computable function of an input word and a pair of a bound , a level and a state with the following property. Let be an input word, a budget, a level, a bound with and , and , states such that a stack certificate shows that takes to at level . Then (5)✦ Let be an instance with admissible analytic constants. For every natural number there are precision parameters , controller tags and a natural number such that (6)✦ Let be an instance with padding whose source machine keeps its space bound and whose analytic constants are admissible with a constant whose bank satisfies . There is a logspace computable function from input words and natural numbers to natural numbers such that, for every input word and every sampling environment over , (7)✦
In the paper, the result reads: for fixed construction constants and admissible , the row, vector and prefix interfaces admit deterministic uniform implementations by restoring queries and cursor motions, for every master environment: queries terminate, return their defined values and restore cursor and catalyst; terminal motions give the specified endpoints; and a root request at clock keeps retained records and uses shared space.
What Is Checked
The claims are stated over logspace computable functions, defined through counter programs with polynomially bounded registers, over controller programs with their budgets and stack certificates, and over instances with the source machine’s space bound, admissible analytic constants, the field size , the sampling environments, the estimator’s contract and the estimator’s value at the start.
The library also proves that logspace computable functions are closed under composition✦ and pairing✦, that constant functions✦, the two projections of a pair, coding✦ and decoding✦ are logspace computable, and that so are the field size , the power of two of the controller’s clock, the decoding of certificates✦, and the lookups, tests and step functions from which the controller programs of the estimator are built.