A Note on Sparse Complete Sets

Cited in

(29)

On polynomial time one-truth-table reducibility to a sparse set
The Fault Tolerance of NP-Hard Problems
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
On symmetric differences of NP-hard sets with weakly P-selective sets
On vanishing of Kronecker coefficients
The fault tolerance of NP-hard problems
On intractability of the classUP
Notes on polynomial levelability
Self-reducible sets of small density
Some Completeness Results on Decision Trees and Group Testing
On sparse hard sets for counting classes
Some consequences of non-uniform conditions on uniform classes
Reductions to sets of low information content (extended abstract)
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
On the number of quantifiers needed to define Boolean functions
On self-reducibility and weak P-selectivity
The Power of Self-Reducibility: Selectivity, Information, and Approximation
Reductions among polynomial isomorphism types
On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts
On inefficient special cases of NP-complete problems
Self-reducibility
Space-efficient recognition of sparse self-reducible languages
Sparse hard sets for P: Resolution of a conjecture of Hartmanis
On the structure of sets in NP and other complexity classes
Padding, commitment and self-reducibility
Monotonous and randomized reductions to sparse sets
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
A note on sparse oracles for NP
A note on P-selective sets and closeness

This page was built for publication: A Note on Sparse Complete Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3051374)