Robustness of probabilistic computational complexity classes under definitional perturbations

DOI10.1016/S0019-9958(82)80019-3MaRDI QIDQ3311661zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stathis Zachos

Publication date 1982

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(82)80019-3

zbMATH Keywords

oraclesprobabilistic algorithmsprobabilistic polynomial-time complexity classesTuring machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Cited in

(10)

• Probabilistic quantifiers and games
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Probabilistic complexity classes and lowness
• Stochastic analog networks and computational complexity
• Competing provers yield improved Karp-Lipton collapse results
• Error-bounded probabilistic computations between MA and AM
• New collapse consequences of NP having small circuits
• Generalized lowness and highness and probabilistic complexity classes
• On closure properties of bounded two-sided error complexity classes
• Stathis Zachos at 70!

This page was built for publication: Robustness of probabilistic computational complexity classes under definitional perturbations

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