Immunity, Relativizations, and Nondeterminism
From MaRDI portal
Publication:3347296
DOI10.1137/0213023zbMATH Open0558.68039OpenAlexW1992789304MaRDI QIDQ3347296FDOQ3347296
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
Recommendations
Cited In (34)
- On simple and creative sets in NP
- On \(\Delta ^ P_ 2\)-immunity
- Set-theoretic structure of computable sets
- Immunity, simplicity, probabilistic complexity classes and relativizations
- A classification of complexity core lattices
- Almost every set in exponential time is P-bi-immune
- Simplicity, immunity, relativizations and nondeterminism
- Resource bounded immunity and simplicity
- A uniform approach to define complexity classes
- A note on separating the relativized polynomial time hierarchy by immune sets
- A second step toward the strong polynomial-time hierarchy
- Classes of bounded nondeterminism
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Bi-immune sets for complexity classes
- On some natural complete operators
- A note on balanced immunity
- Query-monotonic Turing reductions
- Title not available (Why is that?)
- On Some Complexity Characteristics of Immune Sets
- Title not available (Why is that?)
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Immunity and pseudorandomness of context-free languages
- A result relating disjunctive self-reducibility to P-immunity
- Bi-immunity results for cheatable sets
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Strong self-reducibility precludes strong immunity
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Immune Logics ain't that Immune
- Extending finite subsets of an immune set
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- Title not available (Why is that?)
- Immunity for closed sets
- If not empty, NP-P is topologically large
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)
