On Sets Truth-Table Reducible to Sparse Sets

DOI10.1137/0217056zbMath0665.68040OpenAlexW2015568355MaRDI QIDQ3816983

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

sparse setstruth-table reducibilitytally setspolynomial-size circuits

Mathematics Subject Classification ID

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

Related Items (20)

Polynomial-time reducibilities and ``almost all oracle sets ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ A refinement of the low and high hierarchies ⋮ Degrees and reducibilities of easy tally sets ⋮ On lower bounds of the closeness between complexity classes ⋮ On the power of generalized Mod-classes ⋮ Kolmogorov complexity and degrees of tally sets ⋮ Bi-immunity results for cheatable sets ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On sparse hard sets for counting classes ⋮ Reducibilities on tally and sparse sets ⋮ Reductions to sets of low information content ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes ⋮ Distinguishing conjunctive and disjunctive reducibilities by sparse sets ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets ⋮ On adaptive versus nonadaptive bounded query machines

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