theoremnovel

Deterministic approximation of acceptance probability

Approximates acceptance probability within

2^{-q}

in space

O(\log n+q)

precision-parameter form of the fixed-precision theorem

Theorem·thm:probability·§1 Introduction

Statement (paper)

Fix a randomized machine

\mathcal M

with polynomial worst-case running time and

O(\log(n+2))

work space. Let

p_{\mathcal M}(x)

be its acceptance probability on an input

x

of length

n

. There is a uniform deterministic algorithm which, on input

(x,1^q)

with

q\ge1

, outputs an integer

0\le a\le2^{q+2}

satisfying

\left|a2^{-(q+2)}-p_{\mathcal M}(x)\right|\le2^{-q}.

It uses

O(\log(n+2)+q)

work space and

(n+2)^{O(1)}2^{O(q)}

time. The constants depend only on

\mathcal M

In plain English

For a fixed randomized machine

\mathcal M

with polynomial running time and

O(\log(n+2))

work space, a deterministic algorithm given

(x,1^q)

outputs an integer

a

with

0\le a\le 2^{q+2}

such that

a2^{-(q+2)}

is within

2^{-q}

of the acceptance probability

p_{\mathcal M}(x)

. It runs in

O(\log(n+2)+q)

work space and

(n+2)^{O(1)}2^{O(q)}

time.

Why it's here

This is the probability-estimation form of the main result: it gives deterministic approximation of acceptance probabilities to accuracy

2^{-q}

in logarithmic space when

q=O(\log n)

, which is what yields the exact derandomization of logarithmic space. It extends the fixed inverse-polynomial accuracy result (Theorem 12.1) to a precision parameter

q

given in unary, with space growing only additively in

q

Classified novel:

This is the paper's headline probability-estimation form of L = BPL, which is open in prior work: the best earlier deterministic simulations (Saks–Zhou, Hoza) use about log^{3/2} n space. The extension from fixed inverse-polynomial accuracy (Theorem 12.1) to precision 2^{-q} with only additive O(q) space is a main claimed contribution, not a known result.

Uses

thmDeterministic logspace approximation of acceptance probability

Used by

Nothing in the paper

Sources

PaperOpen

Section: §1 Introduction
Page: —
Label: thm:probability
Line: sections/introduction.tex:40

Leannot aligned

Phase 2 aligns this node to a Lean declaration.