Immunity and simplicity in relativizations of probabilistic complexity classes

DOI10.1051/ita/1988220202271zbMath0647.68053OpenAlexW123970995MaRDI QIDQ3792246

José L. Balcázar, David A. Russo

Publication date: 1988

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92307

zbMATH Keywords

probabilistic complexity classesrelativizationoraclessimple setsimmune sets

Mathematics Subject Classification ID

Related Items (5)

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ A uniform approach to define complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Complexity and structure
• Relative complexity of checking and evaluating
• Immunity, Relativizations, and Nondeterminism
• Simplicity, Relativizations and Nondeterminism
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Relativized Questions Involving Probabilistic Algorithms
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computational Complexity of Probabilistic Turing Machines
• Relativized questions involving probabilistic algorithms

This page was built for publication: Immunity and simplicity in relativizations of probabilistic complexity classes