On randomized versus deterministic computation

DOI10.1007/3-540-56939-1_75MaRDI QIDQ4630263zbMATHOpenAlexFDO

Authors 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)

Recommendations

• On randomized versus deterministic computation
• Hardness vs randomness
• On relativized exponential and probabilistic complexity classes
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• scientific article; zbMATH DE number 227415

Cites work

• scientific article; zbMATH DE number 4205978 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1559596 (Why is no real title available?)
• Circuit-size lower bounds and non-reducibility to sparse sets
• On Approximation Algorithms for # P
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• 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

Cited in

(5)

• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• scientific article; zbMATH DE number 1839453 (Why is no real title available?)
• On randomized versus deterministic computation
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Lower space bounds for randomized computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4630263)