SPARSE Reduces Conjunctively to TALLY

DOI10.1137/0224044zbMath0830.68042OpenAlexW2002506919MaRDI QIDQ4852619

Edith Hemaspaandra, Harry Buhrman, Luc Longpré

Publication date: 1 November 1995

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

Full work available at URL: https://ir.cwi.nl/pub/1424

zbMATH Keywords

Kolmogorov complexitytally setconjunctive reductionslow density sets

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Locating \(P\)/poly optimally in the extended low hierarchy ⋮ On monotonous oracle machines ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ On random reductions from sparse sets to tally sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ On hard instances