On the public citation graph

The structure of polynomial complexity cores

https://doi.org/10.1007/bfb0030328
0 signed · 27 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-08860-1_6openalex-snapshot
Relationship between density and deterministic complexity of MP-complete languages
inferredcites →https://doi.org/10.1007/bf01699457openalex-snapshot
Bi-immune sets for complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(82)90002-2openalex-snapshot
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
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.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0210061openalex-snapshot
Completeness, Approximation and Density
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/800061.808770openalex-snapshot
Some structural properties of polynomial reducibilities and sets in NP

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

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/3-540-46691-6_32openalex-snapshot
The Non-recursive Power of Erroneous Computation
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_72openalex-snapshot
Complexity cores and hard problem instances
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_42openalex-snapshot
Kolmogorov Complexity Cores
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/bfb0015769openalex-snapshot
Polynomial levelability and maximal complexity cores
inferred← citeshttps://doi.org/10.1007/bfb0029986openalex-snapshot
NP-hard sets have many hard instances
inferred← citeshttps://doi.org/10.1007/bfb0039600openalex-snapshot
A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees
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/s0304-3975(98)00262-xopenalex-snapshot
On hard instances
inferred← citeshttps://doi.org/10.1109/sct.1988.5283openalex-snapshot
On polynomial and generalized complexity cores
inferred← citeshttps://doi.org/10.1137/0215027openalex-snapshot
Optimal Approximations and Polynomially Levelable Sets
inferred← citeshttps://doi.org/10.1137/0217075openalex-snapshot
P-Printable Sets
inferred← citeshttps://doi.org/10.1145/28869.28880openalex-snapshot
The existence and density of generalized complexity cores
inferred← citeshttps://doi.org/10.31274/rtd-180813-10619openalex-snapshot
On the structure of intractable sets
inferred← citeshttps://doi.org/10.7566/jpsj.82.054801openalex-snapshot
Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup
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.