Probabilistic quantifiers and games
A characterization of classical complexity classes (both deterministic and probabilistic) in terms of the ordinary quantifiers \(\exists\) and \(\forall\) together with a quantifier \(\exists^+\), which means roughly ``for most, is given. Quantifier-swapping principles are presented that reduce many class-inclusion and hierarchy-collapse proofs to straightforward algebraic manipulations. Examples of theorems subsumed by such an approach are: (i) the containment of BPP in the second level of the polynomial hierarchy and (ii) the collapse of the Arthur-Merlin hierarchy to its second level. The paper also includes a chart of class- inclusion and oracle-based separation results.
- A decisive characterization of BPP
- A Fast Monte-Carlo Test for Primality
- A second step toward the polynomial hierarchy
- BPP and the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Does co-NP have short interactive proofs ?
- scientific article; zbMATH DE number 3943795 (Why is no real title available?)
- scientific article; zbMATH DE number 4027449 (Why is no real title available?)
- scientific article; zbMATH DE number 4057011 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 619533 (Why is no real title available?)
- scientific article; zbMATH DE number 3992936 (Why is no real title available?)
- On counting problems and the polynomial-time hierarchy
- On relativized exponential and probabilistic complexity classes
- Probabilistic algorithm for testing primality
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized Questions Involving Probabilistic Algorithms
- Robustness of probabilistic computational complexity classes under definitional perturbations
- Some observations on the probabilistic algorithms and NP-hard problems
- The complexity of facets (and some facets of complexity)
- The knowledge complexity of interactive proof-systems
- The polynomial-time hierarchy
- A uniform approach to define complexity classes
- Polynomial time samplable distributions
- Two queries
- On the probabilistic closure of the loose unambiguous hierarchy
- A probabilistic representation of exact games on image-algebras
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- scientific article; zbMATH DE number 7445154 (Why is no real title available?)
- scientific article; zbMATH DE number 5542577 (Why is no real title available?)
- scientific article; zbMATH DE number 3943795 (Why is no real title available?)
- scientific article; zbMATH DE number 4027449 (Why is no real title available?)
- scientific article; zbMATH DE number 4057011 (Why is no real title available?)
- Structural analysis of the complexity of inverse functions
- Fault-tolerance and complexity (extended abstract)
- scientific article; zbMATH DE number 2089956 (Why is no real title available?)
- scientific article; zbMATH DE number 2102762 (Why is no real title available?)
- On closure properties of bounded two-sided error complexity classes
- scientific article; zbMATH DE number 6130976 (Why is no real title available?)
- scientific article; zbMATH DE number 6787702 (Why is no real title available?)
- Game-Based Probabilistic Predicate Abstraction in PRISM
- Transducing Markov sequences
- ON HIGHER ARTHUR-MERLIN CLASSES
- On counting propositional logic and Wagner's hierarchy
- The Complexity of Aggregates over Extractions by Regular Expressions
- Towards logical foundations for probabilistic computation
- Curry and Howard meet Borel
- On the acceptance power of regular languages
- Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
- Complexity classes of equivalence problems revisited
- Product logic and probabilistic Ulam games
This page was built for publication: Probabilistic quantifiers and games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112019)
