Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets

DOI10.1016/0304-3975(92)90232-5zbMath0755.68050OpenAlexW1987726700WikidataQ126989242 ScholiaQ126989242MaRDI QIDQ1199689

Danilo Bruschi

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90232-5

zbMATH Keywords

relativizationstrong separations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Strong self-reducibility precludes strong immunity ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Resource bounded immunity and simplicity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Simplicity, immunity, relativizations and nondeterminism
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Relativized polynomial hierarchies extending two levels
• Immunity, Relativizations, and Nondeterminism
• A note on separating the relativized polynomial time hierarchy by immune sets
• Simplicity, Relativizations and Nondeterminism
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

This page was built for publication: Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets