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

zbMATH Keywords

probabilistic complexity classesrecursive functionconstructible functionsprobabilistic Turing machineMonte Carlo Turing machine

Mathematics Subject Classification ID

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

On randomized versus deterministic computation, On randomized versus deterministic computation, Lower space bounds for randomized computation, Lower time bounds for randomized computation, A survey of space complexity, Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines, A note on two-dimensional probabilistic Turing machines, Randomness and Intractability in Kolmogorov Complexity, A note on two-dimensional probabilistic finite automata, Amplification of slight probabilistic advantage at absolutely no cost in space

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