Simultaneous strong separations of probabilistic and unambiguous complexity classes

DOI10.1007/BF01368782MaRDI QIDQ3992020zbMATH OpenOpenAlexFDO

Authors David Eppstein, Lane A. Hemaspaandra, James Tisdall, Bülent Yener

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 computationrelativized worldunambiguous computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Relativizations of Unambiguous and Random Polynomial Time Classes
• Hierarchical Unambiguity
• Hierarchical Unambiguity
• Immunity and simplicity in relativizations of probabilistic complexity classes
• scientific article; zbMATH DE number 4114605

Cites work

• BPP and the polynomial hierarchy
• Complexity classes without machines: on complete languages for UP
• Complexity Measures for Public-Key Cryptosystems
• Computational Complexity of Probabilistic Turing Machines
• 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?)
• 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 the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativizations of Unambiguous and Random Polynomial Time Classes
• 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)

• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Separations by random oracles and ``almost classes for generalized reducibilities
• Hierarchical Unambiguity
• scientific article; zbMATH DE number 58312 (Why is no real title available?)
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Fault-tolerance and complexity (extended abstract)
• scientific article; zbMATH DE number 951900 (Why is no real title available?)
• Strong self-reducibility precludes strong immunity
• Languages polylog-time reducible to dot-depth 1/2
• Unimodality, independence lead to NP-hardness of interval probability problems

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)