On Sets Truth-Table Reducible to Sparse Sets

DOI10.1137/0217056MaRDI QIDQ3816983zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Ker-I Ko

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217056

zbMATH Keywords

polynomial-size circuitssparse setstally setstruth-table reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• scientific article; zbMATH DE number 4075037
• Relating Equivalence and Reducibility to Sparse Sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cited in

(32)

• Bounded queries to SAT and the Boolean hierarchy
• Bounds in weak truth-table reducibility
• On polynomial time one-truth-table reducibility to a sparse set
• On sparse hard sets for counting classes
• On 1-truth-table-hard languages
• The structure of logarithmic advice complexity classes
• On symmetric differences of NP-hard sets with weakly P-selective sets
• Geometric sets of low information content
• Some connections between bounded query classes and non-uniform complexity.
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• Polynomial-time reducibilities and ``almost all oracle sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• In Memoriam: Ker-I Ko (1950–2018)
• Reducibilities on tally and sparse sets
• Characterizing polynomial complexity classes by reducibilities
• Schnorr trivial sets and truth-table reducibility
• scientific article; zbMATH DE number 4075037 (Why is no real title available?)
• scientific article; zbMATH DE number 4079403 (Why is no real title available?)
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On lower bounds of the closeness between complexity classes
• scientific article; zbMATH DE number 1318517 (Why is no real title available?)
• Monotonous and randomized reductions to sparse sets
• A refinement of the low and high hierarchies
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
• On the power of generalized Mod-classes
• Degrees and reducibilities of easy tally sets
• Reductions to sets of low information content (extended abstract)
• Very Sparse Leaf Languages
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• On adaptive versus nonadaptive bounded query machines
• Kolmogorov complexity and degrees of tally sets
• Bi-immunity results for cheatable sets

This page was built for publication: On Sets Truth-Table Reducible to Sparse Sets

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