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