Relating Equivalence and Reducibility to Sparse Sets

DOI10.1137/0221034zbMath0761.68039OpenAlexW2076719076MaRDI QIDQ4016912

Osamu Watanabe, Mitsunori Ogiwara, Hemaspaandra, Lane A., Eric W. 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

sparse setsdegreespolynomial-time reducibilities

Mathematics Subject Classification ID

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

Related Items (9)

On monotonous oracle machines ⋮ On the power of generalized Mod-classes ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Polynomial-time compression ⋮ Reductions to sets of low information content ⋮ Bounded queries to arbitrary sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis

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