On the public citation graph

A Note on Sparse Complete Sets

https://doi.org/10.1137/0208034

0 signed · 92 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.1137/0206023openalex-snapshot

On Isomorphisms and Density of $NP$ and Other Complete Sets

What points at this work

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

inferred← citeshttps://doi.org/10.2139/ssrn.4668040openalex-extracted

AI and P Versus NP problem a new method based on artificial intelligence brings us closer to the solution of most important open problem in the theoretical computer science

inferred← citeshttps://doi.org/10.1002/9781118032916.biblioopenalex-snapshot

Bibliography

inferred← citeshttps://doi.org/10.1002/9781118595091.refsopenalex-snapshot

References

inferred← citeshttps://doi.org/10.1002/malq.19850311411openalex-snapshot

On Sparse Complete Sets

inferred← citeshttps://doi.org/10.1006/jcss.1996.0061openalex-snapshot

P-Selective Sets and Reducing Search to Decision vs Self-Reducibility

inferred← citeshttps://doi.org/10.1006/jcss.1998.1615openalex-snapshot

Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis

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-28520-2_3openalex-snapshot

Foundations of Complexity Theory

inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot

Other Public-Key Cryptosystems and Protocols

inferred← citeshttps://doi.org/10.1007/3-540-50517-2_82openalex-snapshot

Padding, commitment and self-reducibility

inferred← citeshttps://doi.org/10.1007/3-540-55719-9_72openalex-snapshot

Reductions to sets of low information content

inferred← citeshttps://doi.org/10.1007/3-540-56287-7_101openalex-snapshot

On bounded truth-table, conjunctive, and randomized reductions to sparse sets

inferred← citeshttps://doi.org/10.1007/3-540-57163-9_24openalex-snapshot

Easily checked self-reducibility

inferred← citeshttps://doi.org/10.1007/3-540-60922-9_26openalex-snapshot

On the existence of hard sparse sets under weak reductions

inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_3openalex-snapshot

Sparse Sets versus Complexity Classes

inferred← citeshttps://doi.org/10.1007/978-1-4612-4478-3_4openalex-snapshot

Juris Hartmanis: Fundamental Contributions to Isomorphism Problems

inferred← citeshttps://doi.org/10.1007/978-1-4612-4478-3_6openalex-snapshot

Self-Reducibility: Effects of Internal Structure on Computational Complexity

inferred← citeshttps://doi.org/10.1007/978-1-4612-4478-3_7openalex-snapshot

The Structure of Complete Degrees

inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_10openalex-snapshot

Sparse Hard Sets for P

inferred← citeshttps://doi.org/10.1007/978-3-030-41672-0_3openalex-snapshot

The Power of Self-Reducibility: Selectivity, Information, and Approximation

inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_29openalex-snapshot

On the Complexity of Kings

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-60322-8_16openalex-snapshot

The Berman-Hartmanis Conjecture and Sparse Sets

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/bf01206639openalex-snapshot

Space-efficient recognition of sparse self-reducible languages

inferred← citeshttps://doi.org/10.1007/bf02006060openalex-snapshot

Notes on polynomial levelability

inferred← citeshttps://doi.org/10.1007/bf02090387openalex-snapshot

On intractability of the classUP

inferred← citeshttps://doi.org/10.1007/bf02090391openalex-snapshot

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

inferred← citeshttps://doi.org/10.1007/bf02090392openalex-snapshot

Self-reducible sets of small density

inferred← citeshttps://doi.org/10.1007/bfb0017127openalex-snapshot

Sparse sets, tally sets, and polynomial reducibilities

inferred← citeshttps://doi.org/10.1007/bfb0022494openalex-snapshot

An essay about research on sparse NP complete sets

inferred← citeshttps://doi.org/10.1007/bfb0030298openalex-snapshot

Sparse oracles, lowness, and highness

inferred← citeshttps://doi.org/10.1007/bfb0039601openalex-snapshot

Self-reducibility

inferred← citeshttps://doi.org/10.1007/bfb0052086openalex-snapshot

A relation between sparse and printable sets in NSPACE(log n)

inferred← citeshttps://doi.org/10.1007/s00037-017-0158-yopenalex-snapshot

On vanishing of Kronecker coefficients

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(82)90002-2openalex-snapshot

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

inferred← citeshttps://doi.org/10.1016/0022-0000(82)90050-2openalex-snapshot

A note on sparse oracles for NP

inferred← citeshttps://doi.org/10.1016/0022-0000(83)90013-2openalex-snapshot

On self-reducibility and weak P-selectivity

inferred← citeshttps://doi.org/10.1016/0022-0000(90)90025-gopenalex-snapshot

Self-reducibility

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/0022-0000(93)90008-kopenalex-snapshot

A note on bi-immunity and p-closeness of p-cheatable sets in P/poly

inferred← citeshttps://doi.org/10.1016/0304-3975(81)90069-4openalex-snapshot

On the structure of sets in NP and other complexity classes

inferred← citeshttps://doi.org/10.1016/0304-3975(83)90020-8openalex-snapshot

Some consequences of non-uniform conditions on uniform classes

inferred← citeshttps://doi.org/10.1016/0304-3975(85)90139-2openalex-snapshot

Reductions among polynomial isomorphism types

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(91)90190-dopenalex-snapshot

Padding, commitment and self-reducibility

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90020-topenalex-snapshot

On sparse hard sets for counting classes

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/j.ic.2010.11.012openalex-snapshot

The fault tolerance of NP-hard problems

inferred← citeshttps://doi.org/10.1016/j.tcs.2009.06.037openalex-snapshot

On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts

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/s0019-9958(86)80032-8openalex-snapshot

A polynomial jump operator

inferred← citeshttps://doi.org/10.1017/9781316716816.003openalex-snapshot

Complete Sets and Structure in Subrecursive Classes

inferred← citeshttps://doi.org/10.1051/ita/1996300201551openalex-snapshot

Monotonous and randomized reductions to sparse sets

inferred← citeshttps://doi.org/10.1109/ccc.2008.21openalex-snapshot

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly

inferred← citeshttps://doi.org/10.1109/focs.2019.00077openalex-snapshot

Hardness Magnification for all Sparse NP Languages

inferred← citeshttps://doi.org/10.1109/sct.1988.5283openalex-snapshot

On polynomial and generalized complexity cores

inferred← citeshttps://doi.org/10.1109/sct.1991.160254openalex-snapshot

On one query, self-reducible sets

inferred← citeshttps://doi.org/10.1109/sct.1992.215396openalex-snapshot

How hard are sparse sets?

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.1995.514863openalex-snapshot

On the structure of low sets [complexity classes]

inferred← citeshttps://doi.org/10.1109/sfcs.1980.40openalex-snapshot

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

inferred← citeshttps://doi.org/10.1109/sfcs.1991.185343openalex-snapshot

Languages that are easier than their proofs

inferred← citeshttps://doi.org/10.1109/sfcs.1995.492492openalex-snapshot

The resolution of a Hartmanis conjecture

inferred← citeshttps://doi.org/10.1137/0210027openalex-snapshot

Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata

inferred← citeshttps://doi.org/10.1137/0212027openalex-snapshot

On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

inferred← citeshttps://doi.org/10.1137/0212038openalex-snapshot

Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

inferred← citeshttps://doi.org/10.1137/0213053openalex-snapshot

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

inferred← citeshttps://doi.org/10.1137/0214003openalex-snapshot

On Circuit-Size Complexity and the Low Hierarchy in NP

inferred← citeshttps://doi.org/10.1137/0215053openalex-snapshot

Sparse Sets, Lowness and Highness

inferred← citeshttps://doi.org/10.1137/0217056openalex-snapshot

On Sets Truth-Table Reducible to Sparse Sets

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/0608062openalex-snapshot

Some Completeness Results on Decision Trees and Group Testing

inferred← citeshttps://doi.org/10.1137/1.9781611973082.46openalex-snapshot

The Power of Nondeterminism in Self-Assembly

inferred← citeshttps://doi.org/10.1137/s0097539792234901openalex-snapshot

Easily Checked Generalized Self-Reducibility

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/3406325.3451007openalex-snapshot

Structure vs. randomness for bilinear maps

inferred← citeshttps://doi.org/10.1145/800141.804678openalex-snapshot

Some connections between nonuniform and uniform complexity classes

inferred← citeshttps://doi.org/10.19086/da.38587openalex-snapshot

Structure vs Randomness for Bilinear Maps

inferred← citeshttps://doi.org/10.20944/preprints201908.0037.v7openalex-snapshot