Relating Equivalence and Reducibility to Sparse Sets

DOI10.1137/0221034MaRDI QIDQ4016912zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Mitsunori Ogiwara, Osamu Watanabe, Eric Allender

Publication date 16 January 1993

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

Full work available at URL http://hdl.handle.net/1802/5124

zbMATH Keywords

degreespolynomial-time reducibilitiessparse sets

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On polynomial time one-truth-table reducibility to a sparse set

Cited in

(17)

• Polynomial-time compression
• The structure of logarithmic advice complexity classes
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Equivalence and lumpability of FSPNs
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• The difference between polynomial-time many-one and truth-table reducibilities on distributional problems
• scientific article; zbMATH DE number 1688354 (Why is no real title available?)
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On Sets Truth-Table Reducible to Sparse Sets
• scientific article; zbMATH DE number 4106273 (Why is no real title available?)
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Bounded queries to arbitrary sets
• Monotonous and randomized reductions to sparse sets
• On the power of generalized Mod-classes
• Upper bounds for the complexity of sparse and tally descriptions
• On monotonous oracle machines
• Reductions to sets of low information content (extended abstract)

This page was built for publication: Relating Equivalence and Reducibility to Sparse Sets

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