On the public citation graph
Nonlevelable sets and immune sets in the accepting density hierarchy inNP
0 signed · 47 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/bf01699457openalex-snapshot
Bi-immune sets for complexity classes
inferredcites →https://doi.org/10.1007/bfb0030328openalex-snapshot
The structure of polynomial complexity cores
inferredcites →https://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(83)90027-2openalex-snapshot
A low and a high hierarchy within NP
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(80)90027-4openalex-snapshot
On counting problems and the polynomial-time hierarchy
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.1016/0304-3975(86)90140-4openalex-snapshot
A classification of complexity core lattices
inferredcites →https://doi.org/10.1016/s0022-0000(73)80028-5openalex-snapshot
A hierarchy for nondeterministic time complexity
inferredcites →https://doi.org/10.1109/sfcs.1976.22openalex-snapshot
On the structure of complete sets: Almost everywhere complexity and infinitely often speedup
inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot
Two theorems on random polynomial time
inferredcites →https://doi.org/10.1109/sfcs.1983.21openalex-snapshot
Generalized Kolmogorov complexity and the structure of feasible computations
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0206049openalex-snapshot
Computational Complexity of Probabilistic Turing Machines
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
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/0211026openalex-snapshot
On the Accepting Density Hierarchy in NP
inferredcites →https://doi.org/10.1137/0213023openalex-snapshot
Immunity, Relativizations, and Nondeterminism
inferredcites →https://doi.org/10.1137/0214003openalex-snapshot
On Circuit-Size Complexity and the Low Hierarchy in NP
inferredcites →https://doi.org/10.1137/0215027openalex-snapshot
Optimal Approximations and Polynomially Levelable Sets
inferredcites →https://doi.org/10.1145/2455.214111openalex-snapshot
Hard-core theorems for complexity classes
inferredcites →https://doi.org/10.1145/321892.321895openalex-snapshot
On Reducibility to Complex or Sparse Sets
inferredcites →https://doi.org/10.1145/322047.322061openalex-snapshot
Separating Nondeterministic Time Complexity Classes
inferredcites →https://doi.org/10.1145/322290.322306openalex-snapshot
Relativized Questions Involving Probabilistic Algorithms
inferredcites →https://doi.org/10.1145/800061.808762openalex-snapshot
A complexity theoretic approach to randomness
inferredcites →https://doi.org/10.1145/800070.802199openalex-snapshot
The complexity of facets (and some facets of complexity)
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
inferredcites →https://doi.org/10.2307/2271876openalex-snapshot
Computational complexity, speedable and levelable sets
inferredcites →https://doi.org/10.2307/2271984openalex-snapshot
On complexity properties of recursively enumerable sets
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/1-4020-8141-3_9openalex-snapshot
Resource Bounded Immunity and Simplicity
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_107openalex-snapshot
Optimal approximations of complete sets
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_99openalex-snapshot
What is a hard instance of a computational problem?
inferred← citeshttps://doi.org/10.1007/978-3-030-41672-0_1openalex-snapshot
In Memoriam: Ker-I Ko (1950–2018)
inferred← citeshttps://doi.org/10.1016/0304-3975(88)90119-3openalex-snapshot
The structure of generalized complexity cores
inferred← citeshttps://doi.org/10.1016/0304-3975(89)90015-7openalex-snapshot
On inefficient special cases of NP-complete problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.03.055openalex-snapshot
Resource bounded immunity and simplicity
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.1109/sct.1990.113974openalex-snapshot
P-productivity and polynomial time approximations
inferred← citeshttps://doi.org/10.1137/0221064openalex-snapshot
Polynomial Time Productivity, Approximations, and Levelability
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.