A Note on Sparse Complete Sets
From MaRDI portal
Publication:3051374
DOI10.1137/0208034zbMath0415.68006OpenAlexW2027466944MaRDI QIDQ3051374
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/7473
Related Items (28)
Reductions among polynomial isomorphism types ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Self-reducibility ⋮ On intractability of the classUP ⋮ Notes on polynomial levelability ⋮ Self-reducible sets of small density ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ On vanishing of Kronecker coefficients ⋮ On the structure of sets in NP and other complexity classes ⋮ A note on sparse oracles for NP ⋮ Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis ⋮ Some Completeness Results on Decision Trees and Group Testing ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ A note on P-selective sets and closeness ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On sparse hard sets for counting classes ⋮ The fault tolerance of NP-hard problems ⋮ Reductions to sets of low information content ⋮ The Fault Tolerance of NP-Hard Problems ⋮ Monotonous and randomized reductions to sparse sets ⋮ On inefficient special cases of NP-complete problems ⋮ On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ On self-reducibility and weak P-selectivity ⋮ Some consequences of non-uniform conditions on uniform classes ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets ⋮ Padding, commitment and self-reducibility
This page was built for publication: A Note on Sparse Complete Sets
