Simultaneous strong separations of probabilistic and unambiguous complexity classes
From MaRDI portal
Publication:3992020
DOI10.1007/BF01368782zbMath0766.68038OpenAlexW2050862278MaRDI QIDQ3992020
Bülent Yener, David Eppstein, Hemaspaandra, Lane A., James Tisdall
Publication date: 28 June 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01368782
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Strong self-reducibility precludes strong immunity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic polynomial time is closed under parity reductions
- BPP and the polynomial hierarchy
- Complexity classes without machines: on complete languages for UP
- Relative complexity of checking and evaluating
- On the unique satisfiability problem
- Immunity, Relativizations, and Nondeterminism
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- Relativizations comparing NP and exponential time
- Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
- Relativizations of Unambiguous and Random Polynomial Time Classes
- Complexity Measures for Public-Key Cryptosystems
- Immunity and simplicity in relativizations of probabilistic complexity classes
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- 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
- Computational Complexity of Probabilistic Turing Machines
- Oracles for Deterministic Versus Alternating Classes
- The isomorphism conjecture fails relative to a random oracle
- On the power of parity polynomial time
