On randomized versus deterministic computation

DOI10.1016/0304-3975(95)00127-1zbMath0877.68053OpenAlexW1530257172MaRDI QIDQ1365675

Marek Karpinski, Rutger Verbeek

Publication date: 9 September 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00127-1

zbMATH Keywords

randomized computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

Lower time bounds for randomized computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Circuit-size lower bounds and non-reducibility to sparse sets
• A taxonomy of problems with fast parallel algorithms
• On Approximation Algorithms for # P
• 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
• Relativized Questions Involving Probabilistic Algorithms

This page was built for publication: On randomized versus deterministic computation