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 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)

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

• 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)

• Hierarchical Unambiguity
• Strong self-reducibility precludes strong immunity
• Fault-tolerance and complexity (extended abstract)
• Separations by random oracles and ``almost classes for generalized reducibilities
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Languages polylog-time reducible to dot-depth 1/2
• Unimodality, independence lead to NP-hardness of interval probability problems
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• 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)