On Sets Truth-Table Reducible to Sparse Sets
From MaRDI portal
Publication:3816983
DOI10.1137/0217056zbMath0665.68040OpenAlexW2015568355MaRDI QIDQ3816983
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
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
