Simultaneous strong separations of probabilistic and unambiguous complexity classes

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

zbMATH Keywords

probabilistic computationunambiguous computationrelativized world

Mathematics Subject Classification ID

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