Distinguishing conjunctive and disjunctive reducibilities by sparse sets

DOI10.1016/0890-5401(89)90029-1MaRDI QIDQ1823690zbMATH OpenOpenAlexFDO

Authors 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

oracle machinesreducibilitiessparse sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Relating Equivalence and Reducibility to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
• scientific article; zbMATH DE number 1318517
• On Sets Truth-Table Reducible to Sparse Sets

Cites work

• A comparison of polynomial time completeness notions
• A comparison of polynomial time reducibilities
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• On Isomorphisms and Density of NP and Other Complete Sets
• On Sets Truth-Table Reducible to Sparse Sets
• On sparse sets in NP-P
• Sets with small generalized Kolmogorov complexity

Cited in

(15)

• On sparse hard sets for counting classes
• On propositional coding techniques for the distinguishability of objects in finite sets
• Sparse and Lopsided Set Disjointness via Information Theory
• scientific article; zbMATH DE number 4179363 (Why is no real title available?)
• In Memoriam: Ker-I Ko (1950–2018)
• Reducibilities on tally and sparse sets
• Relating Equivalence and Reducibility to Sparse Sets
• scientific article; zbMATH DE number 1318517 (Why is no real title available?)
• On the cutting edge of relativization: the resource bounded injury method
• Monotonous and randomized reductions to sparse sets
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
• Upper bounds for the complexity of sparse and tally descriptions
• On monotonous oracle machines
• Reductions to sets of low information content (extended abstract)
• On adaptive versus nonadaptive bounded query machines

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

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