Compressibility and resource bounded measure

DOI10.1137/S0097539797317123MaRDI QIDQ2784485zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Luc Longpré

Publication date 23 April 2002

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

Full work available at URL https://doi.org/10.1137/s0097539797317123

zbMATH Keywords

compressibilityKolmogorov complexityresource bounded measure

Mathematics Subject Classification ID

Classical measure theory (28A99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Compressibility and resource bounded measure
• Compressibility and Kolmogorov complexity
• Compressibility and uniform complexity
• Dimension, entropy rates, and compression
• scientific article; zbMATH DE number 1048036
• scientific article; zbMATH DE number 1335897
• Compressibility of Deterministic and Random Infinite Sequences
• Results on resource-bounded measure
• Compressibility and probabilistic proofs
• Axiomatizing resource bounds for measure

Cited in

(10)

• A stronger Kolmogorov zero-one law for resource-bounded measure
• Dimension is compression
• Entropy compression versus Lovász local lemma
• Compressibility and uniform complexity
• On the Polynomial Depth of Various Sets of Random Strings
• Sub-computable bounded pseudorandomness
• scientific article; zbMATH DE number 1048038 (Why is no real title available?)
• Compressibility of Deterministic and Random Infinite Sequences
• Compressibility and resource bounded measure
• Comparing reductions to NP-complete sets

This page was built for publication: Compressibility and resource bounded measure

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