Simultaneous strong separations of probabilistic and unambiguous complexity classes
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4027449 (Why is no real title available?)
- scientific article; zbMATH DE number 4041255 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 4185033 (Why is no real title available?)
- BPP and the polynomial hierarchy
- Complexity Measures for Public-Key Cryptosystems
- Complexity classes without machines: on complete languages for UP
- Computational Complexity of Probabilistic Turing Machines
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Immunity, Relativizations, and Nondeterminism
- On the power of parity polynomial time
- On the unique satisfiability problem
- Oracles for Deterministic Versus Alternating Classes
- Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
- Probabilistic polynomial time is closed under parity reductions
- Relative complexity of checking and evaluating
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations comparing NP and exponential time
- Relativizations of Unambiguous and Random Polynomial Time Classes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized Questions Involving Probabilistic Algorithms
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- The isomorphism conjecture fails relative to a random oracle
Cited in
(11)- Perfect correspondences between dot-depth and polynomial-time hierarchies
- Separations by random oracles and ``almost classes for generalized reducibilities
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Unimodality, independence lead to NP-hardness of interval probability problems
- Hierarchical Unambiguity
- Languages polylog-time reducible to dot-depth 1/2
- Fault-tolerance and complexity (extended abstract)
- Strong self-reducibility precludes strong immunity
- scientific article; zbMATH DE number 951900 (Why is no real title available?)
- scientific article; zbMATH DE number 58312 (Why is no real title available?)
- Immunity and Simplicity for Exact Counting and Other Counting Classes
This page was built for publication: Simultaneous strong separations of probabilistic and unambiguous complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3992020)
