A randomized machine has a finite control, a read-only input between two endmarkers scanned by finitely many read heads, finitely many binary work tapes, and one fresh fair coin bit at each step. Such a machine is deterministic when its moves do not depend on the coin bits. It works in logarithmic space when the number of distinct work cells it visits on an input of length is . Its acceptance probability on an input at step is the probability, over the coin bits, that it has accepted by step . A language is a set of binary words. The class consists of the languages decided by deterministic logarithmic-space machines that halt on every input. The class consists of the languages for which some logarithmic-space machine halts within steps on every input of length , for constants and , and has acceptance probability at step equal to on inputs outside and at least on inputs in . The class is defined in the same way, with acceptance probability at most on inputs outside and at least on inputs in . The question is whether contains a language outside .
Gill developed the complexity theory of probabilistic Turing machines. Aleliunas, Karp, Lipton, Lovász and Rackoff asked explicitly whether polynomial-time randomized logarithmic space can be simulated in deterministic logarithmic space. The pseudorandom generator of Nisan uses a seed of bits for a space- computation reading random bits. Nisan later simulated bounded-error randomized logarithmic space deterministically in polynomial time and space simultaneously. Saks and Zhou reduced the deterministic space needed for bounded-error logarithmic-space computation to . Hoza improved this space bound to . Reingold placed undirected connectivity in deterministic logarithmic space.
The preprint proves that . It also proves that, for a logarithmic-space randomized machine that halts within steps on every input of length , for constants and , a deterministic algorithm given an input of length and a precision in unary approximates the acceptance probability of the machine on at step to within in space and time ; the Lean library does not contain this result.
The Lean library Logspace proves that and for the classes defined above. It takes no hypothesis. Each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference. Where the preprint states a result differently, its statement is given beside the Lean library’s. The preprint is a guide only, which gives the results their order and their names.
Logspace is a Lean library: 24 items, in nine groups. Each has a page written by OctoInform, listed below.
No item matches.