Lower space bounds for randomized computation
From MaRDI portal
Publication:4632458
DOI10.1007/3-540-58201-0_100zbMath1418.68094MaRDI QIDQ4632458
Marek Karpinski, Rūsiņš Freivalds
Publication date: 29 April 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58201-0_100
Markov chain; probabilistic Turing machines; Monte Carlo Turing machine; word probability; input word
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Lower time bounds for randomized computation, Multihead two-way probabilistic finite automata, Probabilistic rebound Turing machines, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Language recognition power and succinctness of affine automata, Unbounded-error quantum computation with small space bounds, Affine automata verifiers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for probabilistic algorithms for finite state machines
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Non-negative matrices and Markov chains. 2nd ed
- An introduction to randomized algorithms
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Computational Complexity of Probabilistic Turing Machines
- Finite state verifiers I
- On randomized versus deterministic computation
- Estimating a probability using finite memory
- Probabilistic automata
- A context-free language which is not acceptable by a probabilistic automaton
