On the public citation graph

Weakly complete problems are not rare

https://doi.org/10.1007/bf01206322
0 signed · 35 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.1006/jcss.1996.0065openalex-snapshot
Relative to a Random Oracle, NP Is Not Small
inferredcites →https://doi.org/10.1007/3-540-57785-8_159openalex-snapshot
Cook versus Karp-Levin: Separating completeness notions if NP is not small
inferredcites →https://doi.org/10.1007/3-540-58325-4_201openalex-snapshot
Resource bounded randomness and weakly complete problems
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf00538763openalex-snapshot
Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
inferredcites →https://doi.org/10.1007/bf01694181openalex-snapshot
A unified approach to the definition of random sequences
inferredcites →https://doi.org/10.1007/bfb0112458openalex-snapshot
Zufälligkeit und Wahrscheinlichkeit
inferredcites →https://doi.org/10.1016/0022-0000(92)90020-jopenalex-snapshot
Almost everywhere high nonuniform complexity
inferredcites →https://doi.org/10.1016/0304-3975(94)00023-copenalex-snapshot
Almost every set in exponential time is P-bi-immune
inferredcites →https://doi.org/10.1016/0304-3975(95)00189-1openalex-snapshot
Cook versus Karp-Levin: Separating completeness notions if NP is not small
inferredcites →https://doi.org/10.1016/s0019-9958(66)80018-9openalex-snapshot
The definition of random sequences
inferredcites →https://doi.org/10.1016/s0022-0000(73)80030-3openalex-snapshot
Process complexity and effective random tests
inferredcites →https://doi.org/10.1109/sct.1993.336530openalex-snapshot
The quantitative structure of exponential time
inferredcites →https://doi.org/10.1109/sct.1994.315807openalex-snapshot
Relative to a random oracle, NP is not small
inferredcites →https://doi.org/10.1109/sct.1994.315808openalex-snapshot
Weakly hard problems
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/0208013openalex-snapshot
Provably Difficult Combinatorial Games
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/0219076openalex-snapshot
Category and Measure in Complexity Classes
inferredcites →https://doi.org/10.1137/s0097539792237498openalex-snapshot
Measure, Stochasticity, and the Density of Hard Languages
inferredcites →https://doi.org/10.1137/s0097539792238133openalex-snapshot
The Complexity and Distribution of Hard Problems
inferredcites →https://doi.org/10.1137/s0097539793249700openalex-snapshot
Weakly Hard Problems
inferredcites →https://doi.org/10.1145/174652.174659openalex-snapshot
An analysis of ML typability
inferredcites →https://doi.org/10.1145/96709.96748openalex-snapshot
Deciding ML typability is complete for deterministic exponential time
inferredcites →https://doi.org/10.2307/2273858openalex-snapshot
Classifying the computational complexity of problems

What points at this work

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

inferred← citeshttps://doi.org/10.1006/inco.1996.0017openalex-snapshot
Completeness and Weak Completeness under Polynomial-Size Circuits
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_35openalex-snapshot
Almost Complete Sets
inferred← citeshttps://doi.org/10.1007/3-540-59042-0_59openalex-snapshot
Completeness and weak completeness under polynomial-size circuits
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_10openalex-snapshot
The Quantitative Structure of Exponential Time
inferred← citeshttps://doi.org/10.1007/bfb0023487openalex-snapshot
Equivalence of measures of complexity classes
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.01.037openalex-snapshot
A note on measuring in P
inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00262-7openalex-snapshot
Almost complete sets
inferred← citeshttps://doi.org/10.1109/sct.1993.336530openalex-snapshot
The quantitative structure of exponential time
inferred← citeshttps://doi.org/10.1109/sct.1995.514870openalex-snapshot
A small span theorem for P/Poly-Turing reductions
inferred← citeshttps://doi.org/10.1137/s0097539796302269openalex-snapshot
Equivalence of Measures of Complexity Classes
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.