Immunity, Relativizations, and Nondeterminism
From MaRDI portal
Publication:3347296
DOI10.1137/0213023zbMath0558.68039OpenAlexW1992789304MaRDI QIDQ3347296
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
Related Items (22)
On \(\Delta ^ P_ 2\)-immunity ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ A classification of complexity core lattices ⋮ On simple and creative sets in NP ⋮ Query-monotonic Turing reductions ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ OnP-subset structures ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Immunity and pseudorandomness of context-free languages ⋮ Strong self-reducibility precludes strong immunity ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ A uniform approach to define complexity classes ⋮ If not empty, NP-P is topologically large ⋮ Classes of bounded nondeterminism ⋮ Almost every set in exponential time is P-bi-immune ⋮ On some natural complete operators
This page was built for publication: Immunity, Relativizations, and Nondeterminism
