Robustness of probabilistic computational complexity classes under definitional perturbations

DOI10.1016/S0019-9958(82)80019-3zbMath0529.68024OpenAlexW2005440350WikidataQ60060629 ScholiaQ60060629MaRDI QIDQ3311661

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

Turing machinesprobabilistic algorithmsoraclesprobabilistic polynomial-time complexity classes

Mathematics Subject Classification ID

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

Related Items

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