On randomized versus deterministic computation

DOI10.1007/3-540-56939-1_75zbMath1420.68091OpenAlexW2913308506MaRDI QIDQ4630263

Rutger Verbeek, Marek Karpinski

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_75

zbMATH Keywords

polynomial hierarchydeterministic timerandom oracleoracle machineoracle query

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Lower space bounds for randomized computation

Cites Work

• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Circuit-size lower bounds and non-reducibility to sparse sets
• On Approximation Algorithms for # P
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item