Relativized questions involving probabilistic algorithms

DOI10.1145/800133.804363zbMath1282.68158OpenAlexW1993749807MaRDI QIDQ5402574

Charles W. Rackoff

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804363

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Randomized algorithms (68W20) Descriptive complexity and finite models (68Q19)

Related Items

Some results on relativized deterministic and nondeterministic time hierarchies, Some observations on the probabilistic algorithms and NP-hard problems, Immunity and simplicity in relativizations of probabilistic complexity classes, On counting problems and the polynomial-time hierarchy, Randomised algorithms