SPARSE Reduces Conjunctively to TALLY

DOI10.1137/0224044MaRDI QIDQ4852619zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Edith Hemaspaandra, 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

conjunctive reductionsKolmogorov complexitylow density setstally set

Mathematics Subject Classification ID

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

Recommendations

• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
• On polynomial time one-truth-table reducibility to a sparse set
• On random reductions from sparse sets to tally sets
• scientific article; zbMATH DE number 4079403
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cited in

(7)

• Locating P/poly optimally in the extended low hierarchy
• On hard instances
• 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
• On random reductions from sparse sets to tally sets

This page was built for publication: SPARSE Reduces Conjunctively to TALLY

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