Distinguishing conjunctive and disjunctive reducibilities by sparse sets

DOI10.1016/0890-5401(89)90029-1zbMath0681.68066OpenAlexW1968570030MaRDI QIDQ1823690

Ker-I. Ko

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90029-1

zbMATH Keywords

sparse setsreducibilitiesoracle machines

Mathematics Subject Classification ID

Related Items (9)

On monotonous oracle machines ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ 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 ⋮ On adaptive versus nonadaptive bounded query machines

Cites Work

• Unnamed Item
• A comparison of polynomial time completeness notions
• On sparse sets in NP-P
• A comparison of polynomial time reducibilities
• Sets with small generalized Kolmogorov complexity
• On Sets Truth-Table Reducible to Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets

This page was built for publication: Distinguishing conjunctive and disjunctive reducibilities by sparse sets