lemmaroutine

Randomized logspace machines as substochastic systems

Turns a logspace randomized machine into a substochastic system (I−S)−1e(I-S)^{-1}e
bridge from machines to the algebraic transition model
Lemma·lem:model-reduction·§2 The transition model and resource parameters

Statement (paper)

Fix a polynomial-time randomized machine using O(log⁡(n+2))O(\log(n+2)) work space. On an input of length nn one can specify, uniformly in logarithmic space, a polynomial-size vertex set V0V_0, a strictly forward substochastic matrix SS, a vector e∈{0,1}V0e\in\{0,1\}^{V_0}, and a start vertex x0x_0 with the following properties. \begin{enumerate} \item The incoming and outgoing port degrees of SS are bounded by constants depending only on the machine. Port validity, edge weights, and pairing are computable in logarithmic space. \item The vector p0=(I−S)−1ep_0=(I-S)^{-1}e is well defined and belongs to [0,1]V0[0,1]^{V_0}. \item The coordinate p0(x0)p_0(x_0) is the acceptance probability of the machine. \end{enumerate} In particular, an RL\RL computation gives the promise p0(x0)=0p_0(x_0)=0 or p0(x0)≥1/2p_0(x_0)\ge1/2.

In plain English

A polynomial-time randomized machine with O(log⁡(n+2))O(\log(n+2)) work space can be converted, uniformly in logarithmic space, into a polynomial-size vertex set V0V_0, a strictly forward substochastic matrix SS, a vector e∈{0,1}V0e\in\{0,1\}^{V_0} and a start vertex x0x_0. The port degrees of SS are constant, and p0=(I−S)−1ep_0=(I-S)^{-1}e is well defined, lies in [0,1]V0[0,1]^{V_0}, and p0(x0)p_0(x_0) equals the machine's acceptance probability; for an RL machine, p0(x0)p_0(x_0) is 00 or at least 1/21/2.

Why it's here

This lemma links the paper's algebraic transition model to actual randomized logspace computation, so later results about solving (I−S)−1e(I-S)^{-1}e or approximating p0(x0)p_0(x_0) apply to RL and BPL machines. The key point is that the machine's configuration graph can be encoded with bounded port degrees and logspace-computable weights, with acceptance probability read off as one coordinate of the solution.
Classified routine:
Standard encoding of a time-bounded randomized logspace machine as a layered (time-stamped) configuration graph whose absorption probabilities give the acceptance probability, as in classical treatments of RL/BPL (e.g. Saks–Zhou, Nisan). Here it is only repackaged into the paper's substochastic port-degree format.

Uses

Nothing else in the paper

Used by

thmDeterministic logspace approximation of acceptance probabilityclaimStage-L reward approximates acceptance probability

Sources

PaperOpen
Section
§2 The transition model and resource parameters
Page
—
Label
lem:model-reduction
Line
sections/model.tex:18
Leannot aligned

Phase 2 aligns this node to a Lean declaration.