Probabilistic quantifiers and games

DOI10.1016/0022-0000(88)90037-2zbMath0659.03024OpenAlexW2072242455WikidataQ60060632 ScholiaQ60060632MaRDI QIDQ1112019

Stathis Zachos

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90037-2

zbMATH Keywords

polynomial hierarchycomplexity classesBPPcomplexity hierarchiesprobabilistic computationsArthur-Merlin hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On closure properties of bounded two-sided error complexity classes, Structural analysis of the complexity of inverse functions, On counting propositional logic and Wagner's hierarchy, The Complexity of Aggregates over Extractions by Regular Expressions, Two queries, Fault-tolerance and complexity (Extended abstract), On the acceptance power of regular languages, A uniform approach to define complexity classes, Quantum and classical complexity classes: Separations, collapses, and closure properties, Complexity classes of equivalence problems revisited, Polynomial time samplable distributions, Transducing Markov sequences, On the probabilistic closure of the loose unambiguous hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• BPP and the polynomial hierarchy
• The complexity of facets (and some facets of complexity)
• Does co-NP have short interactive proofs ?
• Probabilistic algorithm for testing primality
• Some observations on the probabilistic algorithms and NP-hard problems
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Robustness of probabilistic computational complexity classes under definitional perturbations
• On relativized exponential and probabilistic complexity classes
• 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
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• The knowledge complexity of interactive proof-systems
• A decisive characterization of BPP