Simultaneous strong separations of probabilistic and unambiguous complexity classes

DOI10.1007/BF01368782zbMATH Open0766.68038OpenAlexW2050862278MaRDI QIDQ3992020FDOQ3992020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity classes without machines: on complete languages for UP
• Computational Complexity of Probabilistic Turing Machines
• Complexity Measures for Public-Key Cryptosystems
• BPP and the polynomial hierarchy
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Relative complexity of checking and evaluating
• Relativizations comparing NP and exponential time
• Probabilistic polynomial time is closed under parity reductions
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Title not available (Why is that?)
• The isomorphism conjecture fails relative to a random oracle
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Immunity, Relativizations, and Nondeterminism
• On the unique satisfiability problem
• Title not available (Why is that?)
• Relativized Questions Involving Probabilistic Algorithms
• On the power of parity polynomial time
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• Immunity and simplicity in relativizations of probabilistic complexity classes
• Oracles for Deterministic Versus Alternating Classes
• Relativizations of Unambiguous and Random Polynomial Time Classes
• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)