A note on separating the relativized polynomial time hierarchy by immune sets

DOI10.1051/ita/1990240302291zbMath0701.68032OpenAlexW205047559MaRDI QIDQ3479518

Ker-I. Ko

Publication date: 1990

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

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

zbMATH Keywords

immunityseparationrelativizationcomplexity theoryrelationship between complexity classes

Mathematics Subject Classification ID

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

Related Items

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Strong self-reducibility precludes strong immunity ⋮ Black-Box and Data-Driven Computation ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ A uniform approach to define complexity classes ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties

Cites Work

• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Parity, circuits, and the polynomial-time hierarchy
• Immunity, Relativizations, and Nondeterminism
• Simplicity, Relativizations and Nondeterminism
• Bi-immune sets for complexity classes
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Immunity and simplicity in relativizations of probabilistic complexity classes
• 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
• Relativized Polynomial Time Hierarchies Having Exactly K Levels