On the public citation graph
Immunity, Relativizations, and Nondeterminism
0 signed · 56 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-06841-4_81openalex-snapshot
On Sets Having Only Hard Subsets
inferredcites →https://doi.org/10.1007/bf01699457openalex-snapshot
Bi-immune sets for complexity classes
inferredcites →https://doi.org/10.1016/0096-0551(80)90011-9openalex-snapshot
Introduction to automata theory, languages, and computation
inferredcites →https://doi.org/10.1016/0304-3975(81)90061-xopenalex-snapshot
Bounded query machines: On NP and PSPACE
inferredcites →https://doi.org/10.1016/0304-3975(83)90003-8openalex-snapshot
Oracle-dependent properties of the lattice of NP sets
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0209003openalex-snapshot
Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0210061openalex-snapshot
Completeness, Approximation and Density
inferredcites →https://doi.org/10.1137/0211048openalex-snapshot
Relativizing Time, Space, and Time-Space
inferredcites →https://doi.org/10.1145/2402.322399openalex-snapshot
Refining Nondeterminism in Relativizations of Complexity Classes
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.19990450104openalex-snapshot
Towards the Actual Relationship Between NP and Exponential Time
inferred← citeshttps://doi.org/10.1007/11611257_30openalex-snapshot
P-Selectivity, Immunity, and the Power of One Bit
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_93openalex-snapshot
The boolean hierarchy: Hardware over NP
inferred← citeshttps://doi.org/10.1007/3-540-17179-7_25openalex-snapshot
On simple and creative sets in NP
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot
Other Public-Key Cryptosystems and Protocols
inferred← citeshttps://doi.org/10.1007/3-540-51498-8_2openalex-snapshot
Complexity classes with complete problems between P and NP-C
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_38openalex-snapshot
Almost every set in exponential time is P-bi-immune
inferred← citeshttps://doi.org/10.1007/3-540-57182-5_23openalex-snapshot
On the amount of nondeterminism and the power of verifying
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_7openalex-snapshot
The Complexity of Obtaining Solutions for Problems in NP and NL
inferred← citeshttps://doi.org/10.1007/bf01184814openalex-snapshot
Strong Self-Reducibility Precludes Strong Immunity
inferred← citeshttps://doi.org/10.1007/bf01193574openalex-snapshot
Stacks, queues, and deques with order-statistic operations
inferred← citeshttps://doi.org/10.1007/bf01368782openalex-snapshot
Simultaneous strong separations of probabilistic and unambiguous complexity classes
inferred← citeshttps://doi.org/10.1007/bf01699457openalex-snapshot
Bi-immune sets for complexity classes
inferred← citeshttps://doi.org/10.1007/bf01699469openalex-snapshot
Nonlevelable sets and immune sets in the accepting density hierarchy inNP
inferred← citeshttps://doi.org/10.1007/bf02088009openalex-snapshot
A second step toward the strong polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0024022openalex-snapshot
Combined simplicity and immunity in relativized NP
inferred← citeshttps://doi.org/10.1007/bfb0030286openalex-snapshot
Separating, strongly separating, and collapsing relativized complexity classes
inferred← citeshttps://doi.org/10.1016/0020-0190(90)90191-yopenalex-snapshot
A result relating disjunctive self-reducibility to P-immunity
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00138-3openalex-snapshot
On reductions to sets that avoid EXPSPACE
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90085-4openalex-snapshot
On some natural complete operators
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90140-4openalex-snapshot
A classification of complexity core lattices
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90144-1openalex-snapshot
On simple and creative sets in NP
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90125-yopenalex-snapshot
A uniform approach to define complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90232-5openalex-snapshot
Strong separations of the polynomial hierarchy with oracles: constructive separations by immune and simple sets
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90161-lopenalex-snapshot
If not empty, NP — P is topologically large
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00023-copenalex-snapshot
Almost every set in exponential time is P-bi-immune
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90020-5openalex-snapshot
Simplicity, immunity, relativizations and nondeterminism
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.04.014openalex-snapshot
Query-monotonic Turing reductions
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.07.013openalex-snapshot
Immunity and pseudorandomness of context-free languages
inferred← citeshttps://doi.org/10.1051/ita/1988220202271openalex-snapshot
Immunity and simplicity in relativizations of probabilistic complexity classes
inferred← citeshttps://doi.org/10.1051/ita/1990240302291openalex-snapshot
A note on separating the relativized polynomial time hierarchy by immune sets
inferred← citeshttps://doi.org/10.1051/ita:1999100openalex-snapshot
Immunity and Simplicity for Exact Counting and Other Counting Classes
inferred← citeshttps://doi.org/10.1080/00207168808803679openalex-snapshot
Immunity, simplicity, probabilistic complexity classes and relativizations
inferred← citeshttps://doi.org/10.1137/0214012openalex-snapshot
Simplicity, Relativizations and Nondeterminism
inferred← citeshttps://doi.org/10.1137/0215035openalex-snapshot
Relativizations of Unambiguous and Random Polynomial Time Classes
inferred← citeshttps://doi.org/10.1137/0216042openalex-snapshot
Oracles for Deterministic Versus Alternating Classes
inferred← citeshttps://doi.org/10.1137/0218007openalex-snapshot
The Boolean Hierarchy II: Applications
inferred← citeshttps://doi.org/10.1137/s0097539793258295openalex-snapshot
On the Amount of Nondeterminism and the Power of Verifying
inferred← citeshttps://doi.org/10.1145/28869.28880openalex-snapshot
The existence and density of generalized complexity cores
inferred← citeshttps://doi.org/10.2307/2584070openalex-snapshot
Introduction to the Theory of Complexity.
inferred← citeshttps://doi.org/10.31274/rtd-180813-10619openalex-snapshot
On the structure of intractable sets
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.