On sparse sets in NP-P
From MaRDI portal
Publication:1172386
DOI10.1016/0020-0190(83)90024-8zbMath0501.68014OpenAlexW2069348040MaRDI QIDQ1172386
Publication date: 1983
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(83)90024-8
Related Items (23)
NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Computation times of NP sets of different densities ⋮ On resource-bounded instance complexity ⋮ On intractability of the classUP ⋮ Average-case intractability vs. worst-case intractability ⋮ Limitations of the upward separation technique ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ On the complexity of test case generation for NP-hard problems ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ A note on P-selective sets and closeness ⋮ Logarithmic advice classes ⋮ On random reductions from sparse sets to tally sets ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ On the polynomial IO-complexity ⋮ A positive relativization of polynomial time versus polylog space ⋮ Distinguishing conjunctive and disjunctive reducibilities by sparse sets ⋮ Tally NP sets and easy census functions. ⋮ Sparse sets and collapse of complexity classes ⋮ Towards the Actual Relationship Between NP and Exponential Time ⋮ On one-one polynomial time equivalence relations ⋮ On the computational structure of the connected components of a hard problem
Cites Work
This page was built for publication: On sparse sets in NP-P
