On the public citation graph
Complete sets and closeness to complexity classes
0 signed · 87 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/bf01744434openalex-snapshot
Relativized polynomial hierarchies extending two levels
inferredcites →https://doi.org/10.1007/bfb0030298openalex-snapshot
Sparse oracles, lowness, and highness
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.1016/0022-0000(82)90050-2openalex-snapshot
A note on sparse oracles for NP
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(81)90007-4openalex-snapshot
On γ-reducibility versus polynomial time many-one reducibility
inferredcites →https://doi.org/10.1016/0304-3975(82)90039-1openalex-snapshot
Reductions on NP and P-selective sets
inferredcites →https://doi.org/10.1016/0304-3975(82)90085-8openalex-snapshot
Strong nondeterministic polynomial-time reducibilities
inferredcites →https://doi.org/10.1016/s0019-9958(82)90382-5openalex-snapshot
Circuit-size lower bounds and non-reducibility to sparse sets
inferredcites →https://doi.org/10.1109/sfcs.1982.45openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/swat.1972.29openalex-snapshot
The equivalence problem for regular expressions with squaring requires exponential space
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0207035openalex-snapshot
Polynomial Time Enumeration Reducibility
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/0212027openalex-snapshot
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
inferredcites →https://doi.org/10.1137/0215079openalex-snapshot
Some Observations about the Randomness of Hard Problems
inferredcites →https://doi.org/10.1145/800061.808770openalex-snapshot
Some structural properties of polynomial reducibilities and sets in NP
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
inferredcites →https://doi.org/10.1515/9781400881840openalex-snapshot
Degrees of Unsolvability. (AM-55)
inferredcites →https://doi.org/10.2307/2316720openalex-snapshot
Theory of Recursive Functions and Effective Computability.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11537311_14openalex-snapshot
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies
inferred← citeshttps://doi.org/10.1007/3-540-19488-6_151openalex-snapshot
On ≤1−ttp-sparseness and nondeterministic complexity classes
inferred← citeshttps://doi.org/10.1007/3-540-56279-6_96openalex-snapshot
On symmetric differences of NP-hard sets with weakly-P-selective sets
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_20openalex-snapshot
Splittings, robustness and structure of complete sets
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/978-3-322-95233-2_14openalex-snapshot
Complexity of Closeness, Sparseness and Segment Equivalence for Context-Free and Regular Languages
inferred← citeshttps://doi.org/10.1007/978-3-642-00982-2_32openalex-snapshot
The Fault Tolerance of NP-Hard Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_42openalex-snapshot
Kolmogorov Complexity Cores
inferred← citeshttps://doi.org/10.1007/978-3-662-22110-5_2openalex-snapshot
Complete Sets and Structure in Subrecursive Classes
inferred← citeshttps://doi.org/10.1007/bf01185399openalex-snapshot
A refinement of the low and high hierarchies
inferred← citeshttps://doi.org/10.1007/bf01202282openalex-snapshot
On lower bounds of the closeness between complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0017127openalex-snapshot
Sparse sets, tally sets, and polynomial reducibilities
inferred← citeshttps://doi.org/10.1007/s10472-013-9359-5openalex-snapshot
Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
inferred← citeshttps://doi.org/10.1007/s13748-021-00234-6openalex-snapshot
Existence versus exploitation: the opacity of backdoors and backbones
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00038-eopenalex-snapshot
A note on P-selective sets and closeness
inferred← citeshttps://doi.org/10.1016/0022-0000(92)90015-bopenalex-snapshot
On polynomial time one-truth-table reducibility to a sparse set
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90125-dopenalex-snapshot
Exponential-time and subexponential-time sets
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90292-2openalex-snapshot
On symmetric differences of NP-hard sets with weakly P-selective sets
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00016-6openalex-snapshot
Locating P/poly optimally in the extended low hierarchy
inferred← citeshttps://doi.org/10.1016/0304-3975(95)80016-6openalex-snapshot
Weak completeness in E and E2
inferred← citeshttps://doi.org/10.1016/0304-3975(96)00094-1openalex-snapshot
Reductibility classes of P-selective sets
inferred← citeshttps://doi.org/10.1016/j.artint.2013.11.004openalex-snapshot
The complexity of manipulative attacks in nearly single-peaked electorates
inferred← citeshttps://doi.org/10.1016/j.ic.2010.11.012openalex-snapshot
The fault tolerance of NP-hard problems
inferred← citeshttps://doi.org/10.1016/j.ipl.2007.02.018openalex-snapshot
Robustness of PSPACE-complete sets
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.05.001openalex-snapshot
Frequency of correctness versus average polynomial time
inferred← citeshttps://doi.org/10.1017/9781316716816.003openalex-snapshot
Complete Sets and Structure in Subrecursive Classes
inferred← citeshttps://doi.org/10.1051/ita/1996300201011openalex-snapshot
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313839openalex-snapshot
Properties of NP-complete sets
inferred← citeshttps://doi.org/10.1109/sct.1988.5283openalex-snapshot
On polynomial and generalized complexity cores
inferred← citeshttps://doi.org/10.1109/sct.1991.160264openalex-snapshot
Relating equivalence and reducibility to sparse sets
inferred← citeshttps://doi.org/10.1109/sct.1991.160265openalex-snapshot
Exponential time and subexponential time sets
inferred← citeshttps://doi.org/10.1109/sct.1992.215398openalex-snapshot
On closeness of NP-hard sets to other complexity classes
inferred← citeshttps://doi.org/10.1109/sct.1993.336530openalex-snapshot
The quantitative structure of exponential time
inferred← citeshttps://doi.org/10.1109/sct.1994.315811openalex-snapshot
On the structure of complete sets
inferred← citeshttps://doi.org/10.1137/0217056openalex-snapshot
On Sets Truth-Table Reducible to Sparse Sets
inferred← citeshttps://doi.org/10.1137/0219076openalex-snapshot
Category and Measure in Complexity Classes
inferred← citeshttps://doi.org/10.1137/0220030openalex-snapshot
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
inferred← citeshttps://doi.org/10.1137/0221034openalex-snapshot
Relating Equivalence and Reducibility to Sparse Sets
inferred← citeshttps://doi.org/10.1137/s009753970444421xopenalex-snapshot
Properties of NP‐Complete Sets
inferred← citeshttps://doi.org/10.1137/s0097539792225935openalex-snapshot
Closeness of NP-Hard Sets to Other Complexity Classes
inferred← citeshttps://doi.org/10.1137/s0097539795279724openalex-snapshot
Splittings, Robustness, and Structure of Complete Sets
inferred← citeshttps://doi.org/10.1142/9789812794499_0034openalex-snapshot
A View of Structural Complexity Theory
inferred← citeshttps://doi.org/10.1145/100216.100276openalex-snapshot
On polynomial time bounded truth-table reducibility of NP sets to sparse sets
inferred← citeshttps://doi.org/10.1145/147508.147546openalex-snapshot
Lower bounds for the low hierarchy
inferred← citeshttps://doi.org/10.1145/1839676.1839696openalex-snapshot
Using complexity to protect elections
inferred← citeshttps://doi.org/10.1145/2000378.2000406openalex-snapshot
The complexity of manipulative attacks in nearly single-peaked electorates
inferred← citeshttps://doi.org/10.1145/2421119.2421135openalex-snapshot
SIGACT News Complexity Theory Column 76
inferred← citeshttps://doi.org/10.1145/261342.261344openalex-snapshot
Raising NP lower bounds to parallel NP lower bounds
inferred← citeshttps://doi.org/10.1613/jair.3136openalex-snapshot
Multimode Control Attacks on Elections
inferred← citeshttps://doi.org/10.21236/ada300061openalex-snapshot
Polynomial-Time Semi-Rankable Sets.
inferred← citeshttps://doi.org/10.48550/arxiv.1007.1800openalex-snapshot
Multimode Control Attacks on Elections
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.