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
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
