Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

DOI10.1137/0212038zbMath0532.68051OpenAlexW2055734996MaRDI QIDQ3314997

Esko Ukkonen

Publication date: 1983

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

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

zbMATH Keywords

polynomial timetruth-table reductionTuring reductionsparse setreducibilitieshard set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (11)

Space-efficient recognition of sparse self-reducible languages ⋮ Sparse sets, approximable sets, and parallel queries to NP ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ On the power of parity polynomial time ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On polynomial-time Turing and many-one completeness in PSPACE ⋮ On the power of parity polynomial time ⋮ On sparse hard sets for counting classes ⋮ Reductions to sets of low information content ⋮ Monotonous and randomized reductions to sparse sets ⋮ Some consequences of non-uniform conditions on uniform classes

This page was built for publication: Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets