On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
DOI10.1016/0890-5401(87)90057-5zbMath0631.68047OpenAlexW1992055577WikidataQ56039186 ScholiaQ56039186MaRDI QIDQ1094874
Marek Karpinski, Rutger Verbeek
Publication date: 1987
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(87)90057-5
probabilistic complexity classesrecursive functionconstructible functionsprobabilistic Turing machineMonte Carlo Turing machine
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Halting space-bounded computations
- Projections of languages recognizable by probabilistic and alternating finite multitape automata
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Lower bounds on space complexity for contextfree recognition
- Randomised algorithms
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- A Fast Monte-Carlo Test for Primality
- Computational Complexity of Probabilistic Turing Machines
- An Approach to a Unified Theory of Automata