Relativized questions involving probabilistic algorithms

DOI10.1145/800133.804363MaRDI QIDQ5402574zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 168445
• Probabilistic Algorithmic Knowledge
• scientific article; zbMATH DE number 3870594
• On relativized probabilistic polynomial time algorithms
• A generalized characterization of algorithmic probability
• Algorithmic Probability: Theory and Applications
• Probability metrics and recursive algorithms
• scientific article; zbMATH DE number 846908

Cited in

(5)

• 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
• Some results on relativized deterministic and nondeterministic time hierarchies
• Randomised algorithms

This page was built for publication: Relativized questions involving probabilistic algorithms

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