On randomized versus deterministic computation

DOI10.1007/3-540-56939-1_75zbMATH Open1420.68091OpenAlexW2913308506MaRDI QIDQ4630263FDOQ4630263

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

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

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)

Cites Work

• On Approximation Algorithms for # P
• Title not available (Why is that?)
• Circuit-size lower bounds and non-reducibility to sparse sets
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Title not available (Why is that?)

Cited In (4)

• On using deterministic functions to reduce randomness in probabilistic algorithms
• Title not available (Why is that?)
• On randomized versus deterministic computation
• 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)