On the public citation graph
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
0 signed · 102 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-08860-1_6openalex-snapshot
Relationship between density and deterministic complexity of MP-complete languages
inferredcites →https://doi.org/10.1007/3-540-16486-3_85openalex-snapshot
The complexity of sparse sets in P
inferredcites →https://doi.org/10.1007/3-540-19488-6_151openalex-snapshot
On ≤1−ttp-sparseness and nondeterministic complexity classes
inferredcites →https://doi.org/10.1007/bf01744288openalex-snapshot
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
inferredcites →https://doi.org/10.1007/bf01768464openalex-snapshot
Inclusion complete tally languages and the Hartmanis-Berman conjecture
inferredcites →https://doi.org/10.1016/0020-0190(76)90097-1openalex-snapshot
Relative complexity of checking and evaluating
inferredcites →https://doi.org/10.1016/0020-0190(88)90071-3openalex-snapshot
On hardness of one-way functions
inferredcites →https://doi.org/10.1016/0022-0000(81)90068-4openalex-snapshot
Some observations on NP real numbers and P-selective sets
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)90013-2openalex-snapshot
On self-reducibility and weak P-selectivity
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/0022-0000(89)90024-xopenalex-snapshot
PNP[(log )] and sparse turing-complete sets for 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(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
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)90122-0openalex-snapshot
More on the power of chain rules in context-free grammars
inferredcites →https://doi.org/10.1016/0304-3975(83)90020-8openalex-snapshot
Some consequences of non-uniform conditions on uniform classes
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/s0019-9958(74)90473-2openalex-snapshot
Tally languages and complexity classes
inferredcites →https://doi.org/10.1016/s0019-9958(82)80084-3openalex-snapshot
Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
inferredcites →https://doi.org/10.1016/s0019-9958(84)80053-4openalex-snapshot
An average case analysis of Floyd's algorithm to construct heaps
inferredcites →https://doi.org/10.1016/s0019-9958(84)80056-xopenalex-snapshot
The complexity of promise problems with applications to public-key cryptography
inferredcites →https://doi.org/10.1090/s0002-9947-1965-0170805-7openalex-snapshot
On the Computational Complexity of Algorithms
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/psct.1987.10319251openalex-snapshot
A Structural Theorem that Depends Quantitatively on the Complexity of SAT
inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot
Two theorems on random polynomial time
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/0212027openalex-snapshot
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
inferredcites →https://doi.org/10.1137/0212038openalex-snapshot
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
inferredcites →https://doi.org/10.1137/0214003openalex-snapshot
On Circuit-Size Complexity and the Low Hierarchy in NP
inferredcites →https://doi.org/10.1137/0214043openalex-snapshot
On Restricting the Size of Oracles Compared with Restricting Access to Oracles
inferredcites →https://doi.org/10.1137/0217018openalex-snapshot
Complexity Measures for Public-Key Cryptosystems
inferredcites →https://doi.org/10.1137/0217038openalex-snapshot
Erratum: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
inferredcites →https://doi.org/10.1137/0217056openalex-snapshot
On Sets Truth-Table Reducible to Sparse Sets
inferredcites →https://doi.org/10.1145/100216.100276openalex-snapshot
On polynomial time bounded truth-table reducibility of NP sets to sparse sets
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
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.2001.3072openalex-snapshot
Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph
inferred← citeshttps://doi.org/10.1006/jcss.1996.0062openalex-snapshot
P-Selective Self-Reducible Sets: A New Characterization of P
inferred← citeshttps://doi.org/10.1007/11549345_42openalex-snapshot
Combining Self-reducibility and Partial Information Algorithms
inferred← citeshttps://doi.org/10.1007/3-540-44679-6_6openalex-snapshot
Algebraic Properties for P-Selectivity
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_53openalex-snapshot
Structural analyses on the complexity of inverting functions
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-57785-8_160openalex-snapshot
On sets bounded truth-table reducible to P-selective sets
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_7openalex-snapshot
The complexity of generating and checking proofs of membership
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_7openalex-snapshot
The Complexity of Obtaining Solutions for Problems in NP and NL
inferred← citeshttps://doi.org/10.1007/978-3-540-24698-5_13openalex-snapshot
The Complexity of Finding Top-Toda-Equivalence-Class Members
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_40openalex-snapshot
On the Advice Complexity of Tournaments
inferred← citeshttps://doi.org/10.1007/b104335openalex-snapshot
List Decoding of Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/bf01202283openalex-snapshot
Structural analysis of the complexity of inverse functions
inferred← citeshttps://doi.org/10.1007/bf02679445openalex-snapshot
On sets turing reducible to p-selective sets
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.1016/0020-0190(95)00073-lopenalex-snapshot
Some results on selectivity and self-reducibility
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
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)00080-3openalex-snapshot
Computing functions with parallel queries to NP
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00167-0openalex-snapshot
Quasi-linear truth-table reductions to p-selective sets
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.cam.2004.03.003openalex-snapshot
The arbitrary order implicit multistep schemes of exponential fitting and their applications
inferred← citeshttps://doi.org/10.1016/j.ipl.2007.02.018openalex-snapshot
Robustness of PSPACE-complete sets
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.03.003openalex-snapshot
On the reducibility of sets inside NP to sets with low information content
inferred← citeshttps://doi.org/10.1016/s0020-0190(96)00189-5openalex-snapshot
NP-hard sets are superterse unless NP is small
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80009-1openalex-snapshot
A taxonomy of complexity classes of functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00147-5openalex-snapshot
On the complexity of data disjunctions
inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00082-3openalex-snapshot
Query complexity of membership comparable sets
inferred← citeshttps://doi.org/10.1051/ita/1996300201351openalex-snapshot
On sets bounded truth-table reducible to $P$-selective sets
inferred← citeshttps://doi.org/10.1051/ita/1996300201551openalex-snapshot
Monotonous and randomized reductions to sparse sets
inferred← citeshttps://doi.org/10.1109/ccc.1996.507684openalex-snapshot
A note on p-selective sets and on adaptive versus nonadaptive queries to NP
inferred← citeshttps://doi.org/10.1109/ccc.1997.612295openalex-snapshot
Six hypotheses in search of a theorem
inferred← citeshttps://doi.org/10.1109/ccc.1998.694584openalex-snapshot
On membership comparable sets
inferred← citeshttps://doi.org/10.1109/ccc.1999.766273openalex-snapshot
Quantum bounded query complexity
inferred← citeshttps://doi.org/10.1109/ccc.2001.933875openalex-snapshot
Separation of NP-completeness notions
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313839openalex-snapshot
Properties of NP-complete sets
inferred← citeshttps://doi.org/10.1109/sct.1992.215387openalex-snapshot
On the nonuniform complexity of the graph isomorphism problem
inferred← citeshttps://doi.org/10.1109/sct.1993.336519openalex-snapshot
Computing functions with parallel queries to NP
inferred← citeshttps://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
inferred← citeshttps://doi.org/10.1109/sct.1993.336541openalex-snapshot
P-selective sets, and reducing search to decision vs. self-reducibility
inferred← citeshttps://doi.org/10.1109/sct.1993.336542openalex-snapshot
P-selective self-reducibles sets: a new characterization of P
inferred← citeshttps://doi.org/10.1109/sct.1994.315818openalex-snapshot
Using bounded query classes to separate classes in the exponential time hierarchy from classes in PH
inferred← citeshttps://doi.org/10.1109/sct.1994.315821openalex-snapshot
Polynomial time truth-table reductions to p-selective sets
inferred← citeshttps://doi.org/10.1109/sct.1994.315823openalex-snapshot
Polynomial-time membership comparable sets
inferred← citeshttps://doi.org/10.1109/sct.1995.514863openalex-snapshot
On the structure of low sets [complexity classes]
inferred← citeshttps://doi.org/10.1137/s0097539701387039openalex-snapshot
Separation of NP-Completeness Notions
inferred← citeshttps://doi.org/10.1137/s0097539703427550openalex-snapshot
Algebraic Properties for Selector Functions
inferred← citeshttps://doi.org/10.1137/s009753970444421xopenalex-snapshot
Properties of NP‐Complete Sets
inferred← citeshttps://doi.org/10.1137/s0097539793258131openalex-snapshot
Polynomial-Time Membership Comparable Sets
inferred← citeshttps://doi.org/10.1137/s0097539794261970openalex-snapshot
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
inferred← citeshttps://doi.org/10.1137/s0097539795279724openalex-snapshot
Splittings, Robustness, and Structure of Complete Sets
inferred← citeshttps://doi.org/10.1145/1122480.1122495openalex-snapshot
Open questions in the theory of semifeasible computation
inferred← citeshttps://doi.org/10.31274/etd-180810-4556openalex-snapshot
Randomness in completeness and space-bounded computations
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.