On the public citation graph
Bi-immune sets for complexity classes
0 signed · 126 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.1016/0022-0000(78)90034-xopenalex-snapshot
On splitting recursive sets
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
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.1051/ita/197408r100371openalex-snapshot
Une généralisation de la notion d'ensemble immune
inferredcites →https://doi.org/10.1090/s0002-9904-1944-08111-1openalex-snapshot
Recursively enumerable sets of positive integers and their decision 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.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/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/0213023openalex-snapshot
Immunity, Relativizations, and Nondeterminism
inferredcites →https://doi.org/10.1137/0214012openalex-snapshot
Simplicity, Relativizations and Nondeterminism
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.1002/malq.19990450104openalex-snapshot
Towards the Actual Relationship Between NP and Exponential Time
inferred← citeshttps://doi.org/10.1002/malq.200920043openalex-snapshot
Low sets without subsets of higher many-one degree
inferred← citeshttps://doi.org/10.1006/inco.1996.0017openalex-snapshot
Completeness and Weak Completeness under Polynomial-Size Circuits
inferred← citeshttps://doi.org/10.1007/1-4020-8141-3_9openalex-snapshot
Resource Bounded Immunity and Simplicity
inferred← citeshttps://doi.org/10.1007/11549345_34openalex-snapshot
Autoreducibility, Mitoticity, and Immunity
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_106openalex-snapshot
The topology of provability in complexity theory
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_97openalex-snapshot
Resource-bounded Kolmogorov complexity of hard languages
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-16761-7_86openalex-snapshot
Lower bounds by recursion theoretic arguments
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-44683-4_50openalex-snapshot
Partial Information and Special Case Algorithms
inferred← citeshttps://doi.org/10.1007/3-540-45066-1_7openalex-snapshot
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_33openalex-snapshot
Bi-Immunity Separates Strong NP-Completeness Notions
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_18openalex-snapshot
Distributionally-Hard Languages
inferred← citeshttps://doi.org/10.1007/3-540-52282-4_27openalex-snapshot
A note on the almost-everywhere hierarchy for nondeterministic time
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_71openalex-snapshot
Algorithms from complexity theory: Polynomial-time operations for complex sets
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_72openalex-snapshot
Complexity cores and hard problem instances
inferred← citeshttps://doi.org/10.1007/3-540-53504-7_60openalex-snapshot
Almost-everywhere complexity, bi-immunity and nondeterministic space
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_44openalex-snapshot
On strong separations from AC o
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-58325-4_228openalex-snapshot
Definition and existence of super complexity cores
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_57openalex-snapshot
E-complete sets do not have optimal polynomial time approximations
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_69openalex-snapshot
Genericity and measure for exponential time
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/3-540-60084-1_90openalex-snapshot
On optimal polynomial time approximations: P-levelability vs. δ-levelability
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_28openalex-snapshot
Fine separation of average time complexity classes
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-030-04618-7_23openalex-snapshot
A New Algorithm Design Technique for Hard Problems, Building on Methods of Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_28openalex-snapshot
Hardness Hypotheses, Derandomization, and Circuit Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-29344-3_29openalex-snapshot
Structural Complexity of Multiobjective NP Search Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-77735-6_4openalex-snapshot
Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness
inferred← citeshttps://doi.org/10.1007/bf01184814openalex-snapshot
Strong Self-Reducibility Precludes Strong Immunity
inferred← citeshttps://doi.org/10.1007/bf01200120openalex-snapshot
Relativized isomorphisms of NP-complete sets
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/bf01704904openalex-snapshot
Complete sets and closeness to complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0015769openalex-snapshot
Polynomial levelability and maximal complexity cores
inferred← citeshttps://doi.org/10.1007/bfb0030328openalex-snapshot
The structure of polynomial complexity cores
inferred← citeshttps://doi.org/10.1007/bfb0030859openalex-snapshot
Sets computable in polynomial time on average
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.1007/s00224-005-1211-9openalex-snapshot
The Complexity of Finding Top-Toda-Equivalence-Class Members
inferred← citeshttps://doi.org/10.1007/s00224-007-9000-2openalex-snapshot
Partial Bi-immunity, Scaled Dimension, and NP-Completeness
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90181-5openalex-snapshot
On solving hard problems by polynomial-size circuits
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/0022-0000(88)90036-0openalex-snapshot
The topology of provability in complexity theory
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90021-4openalex-snapshot
Some consequences of the existence of pseudorandom generators
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90023-8openalex-snapshot
Honest polynomial time reducibilities and the P=?NP problem
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90218-xopenalex-snapshot
On one-one polynomial time equivalence relations
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(87)90132-0openalex-snapshot
A comparison of polynomial time completeness notions
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/0304-3975(90)90177-jopenalex-snapshot
Bi-immunity results for cheatable sets
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90117-copenalex-snapshot
Almost-everywhere complexity hierarchies for nondeterministic time
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)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/0304-3975(95)00146-8openalex-snapshot
Index sets and presentations of complexity classes
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)89424-2openalex-snapshot
Genericity and measure for exponential time
inferred← citeshttps://doi.org/10.1016/0890-5401(90)90052-jopenalex-snapshot
Kolmogorov complexity and degrees of tally sets
inferred← citeshttps://doi.org/10.1016/0890-5401(91)90022-topenalex-snapshot
A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.10.020openalex-snapshot
Autoreducibility, mitoticity, and immunity
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.10.003openalex-snapshot
Recursion-theoretic ranking and compression
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.03.055openalex-snapshot
Resource bounded immunity and simplicity
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.07.013openalex-snapshot
Immunity and pseudorandomness of context-free languages
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.03.012openalex-snapshot
A new algorithm design technique for hard problems
inferred← citeshttps://doi.org/10.1016/s0019-9958(86)80024-9openalex-snapshot
The density and complexity of polynomial cores for intractable sets
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00295-9openalex-snapshot
Complete distributional problems, hard languages, and resource-bounded measure
inferred← citeshttps://doi.org/10.1017/jsl.2024.44openalex-snapshot
A PARAMETERIZED HALTING PROBLEM, $ \Delta _0$ TRUTH AND THE MRDP THEOREM
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/ccc.2001.933875openalex-snapshot
Separation of NP-completeness notions
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313842openalex-snapshot
Partial Bi-immunity and NP-completeness
inferred← citeshttps://doi.org/10.1109/ccc.2004.23openalex-snapshot
Partial bi-immunity and NP-completeness
inferred← citeshttps://doi.org/10.1109/sct.1989.41814openalex-snapshot
Finitary substructure languages with application to the theory of NP-completeness
inferred← citeshttps://doi.org/10.1109/sct.1991.160265openalex-snapshot
Exponential time and subexponential time 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.514857openalex-snapshot
A note on genericity and bi-immunity
inferred← citeshttps://doi.org/10.1109/sfcs.1984.715952openalex-snapshot
Complexity Measures For Public-Key Cryptosystems
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366869openalex-snapshot
The complexity and distribution of hard problems
inferred← citeshttps://doi.org/10.1137/0213023openalex-snapshot
Immunity, Relativizations, and Nondeterminism
inferred← citeshttps://doi.org/10.1137/0215027openalex-snapshot
Optimal Approximations and Polynomially Levelable Sets
inferred← citeshttps://doi.org/10.1137/0215079openalex-snapshot
Some Observations about the Randomness of Hard Problems
inferred← citeshttps://doi.org/10.1137/0216042openalex-snapshot
Oracles for Deterministic Versus Alternating Classes
inferred← citeshttps://doi.org/10.1137/0217018openalex-snapshot
Complexity Measures for Public-Key Cryptosystems
inferred← citeshttps://doi.org/10.1137/0217056openalex-snapshot
On Sets Truth-Table Reducible to Sparse Sets
inferred← citeshttps://doi.org/10.1137/s0097539701387039openalex-snapshot
Separation of NP-Completeness Notions
inferred← citeshttps://doi.org/10.1137/s0097539792238133openalex-snapshot
The Complexity and Distribution of Hard Problems
inferred← citeshttps://doi.org/10.1137/s0097539796311715openalex-snapshot
Fine Separation of Average-Time Complexity Classes
inferred← citeshttps://doi.org/10.1145/28869.28880openalex-snapshot
The existence and density of generalized complexity cores
inferred← citeshttps://doi.org/10.1145/3209108.3209155openalex-snapshot
A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
inferred← citeshttps://doi.org/10.1145/62029.62030openalex-snapshot
Unification: a multidisciplinary survey
inferred← citeshttps://doi.org/10.1145/882116.882125openalex-snapshot
SIGACT news complexity theory column 40
inferred← citeshttps://doi.org/10.1305/ndjfl/1117755150openalex-snapshot
Sets without Subsets of Higher Many-One Degree
inferred← citeshttps://doi.org/10.31274/rtd-180813-10619openalex-snapshot
On the structure of intractable sets
inferred← citeshttps://doi.org/10.31274/rtd-180813-11836openalex-snapshot
The complexity and distribution of computationally useful problems
inferred← citeshttps://doi.org/10.3233/com-200296openalex-snapshot
Degrees of sets having no subsets of higher m - and tt-degree
inferred← citeshttps://doi.org/10.3233/fi-2011-546openalex-snapshot
Characterizations and Existence of Easy Sets without Hard Subsets
inferred← citeshttps://doi.org/10.37236/1942openalex-snapshot
A Relationship between the Major Index for Tableaux and the Charge Statistic for Permutations
inferred← citeshttps://doi.org/10.48550/arxiv.1602.02432openalex-snapshot
A Finitely presented group whose word problem has sampleable hard instances
inferred← citeshttps://doi.org/10.48550/arxiv.1608.08679openalex-snapshot
Roughly Polynomial Time: A Concept of Tractability Covering All Known Natural NP-complete Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1709.04699openalex-snapshot
Levelable Sets and the Algebraic Structure of Parameterizations
inferred← citeshttps://doi.org/10.5539/jmr.v9n4p69openalex-snapshot
Cone Avoidance of Some Turing Degrees
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.