Immunity, Relativizations, and Nondeterminism

DOI10.1137/0213023MaRDI QIDQ3347296zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Uwe Schöning

Publication date 1984

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0213023

zbMATH Keywords

complexity classesNPPbounded queriesimmune setsoracle machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Immunity, simplicity, probabilistic complexity classes and relativizations
• Bi-immune sets for complexity classes
• A note on separating the relativized polynomial time hierarchy by immune sets
• Immunity and simplicity in relativizations of probabilistic complexity classes
• On \(\Delta ^ P_ 2\)-immunity

Cited in

(35)

• Almost every set in exponential time is P-bi-immune
• Strong self-reducibility precludes strong immunity
• Query-monotonic Turing reductions
• A second step toward the strong polynomial-time hierarchy
• A result relating disjunctive self-reducibility to P-immunity
• Immunity and pseudorandomness of context-free languages
• Immune Logics ain't that Immune
• Bi-immunity results for cheatable sets
• Immunity of complete problems
• On some natural complete operators
• A uniform approach to define complexity classes
• Immunity for closed sets
• A note on separating the relativized polynomial time hierarchy by immune sets
• Classes of bounded nondeterminism
• On simple and creative sets in NP
• A note on balanced immunity
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• If not empty, NP-P is topologically large
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Resource bounded immunity and simplicity
• scientific article; zbMATH DE number 1665448 (Why is no real title available?)
• scientific article; zbMATH DE number 2163012 (Why is no real title available?)
• scientific article; zbMATH DE number 1962844 (Why is no real title available?)
• A classification of complexity core lattices
• Simplicity, immunity, relativizations and nondeterminism
• Immunity and simplicity in relativizations of probabilistic complexity classes
• On Some Complexity Characteristics of Immune Sets
• Bi-immune sets for complexity classes
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Immunity, simplicity, probabilistic complexity classes and relativizations
• On \(\Delta ^ P_ 2\)-immunity
• Extending finite subsets of an immune set
• Set-theoretic structure of computable sets
• OnP-subset structures
• Immunity and Simplicity for Exact Counting and Other Counting Classes

This page was built for publication: Immunity, Relativizations, and Nondeterminism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347296)