On tape-bounded probabilistic Turing machine acceptors

DOI10.1016/0304-3975(81)90032-3zbMath0473.68044OpenAlexW1974216994MaRDI QIDQ1158756

Janos Simon

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90032-3

zbMATH Keywords

deterministic and probabilistic tape complexities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On counting propositional logic and Wagner's hierarchy, Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Division in idealized unit cost RAMs, Relationships among $PL$, $\#L$, and the determinant, Decreasing the bandwidth of a transition matrix, A survey of space complexity, The time-precision tradeoff problem on on-line probabilistic Turing machines, Probabilistic Turing machines and recursively enumerable Dedekind cuts

Cites Work

• A characterization of the power of vector machines
• Relationships between nondeterministic and deterministic tape complexities
• Fast Parallel Matrix Inversion Algorithms
• Computational Complexity of Probabilistic Turing Machines
• Probabilistic Turing Machines and Computability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item