Simplicity, immunity, relativizations and nondeterminism

DOI10.1016/0890-5401(89)90020-5zbMath0664.68049OpenAlexW2039789519MaRDI QIDQ1115610

Leen Torenvliet, Peter van Emde Boas

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90020-5

zbMATH Keywords

relativizationoracleNPcoNPsimple setsimmune sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (5)

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Strong self-reducibility precludes strong immunity ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ Resource bounded immunity and simplicity

Cites Work

• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Indexings of subrecursive classes
• The polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Immunity, Relativizations, and Nondeterminism
• Relativizations comparing NP and exponential time
• 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
• Recursive Predicates and Quantifiers

This page was built for publication: Simplicity, immunity, relativizations and nondeterminism