Compressibility and Resource Bounded Measure

DOI10.1137/S0097539797317123zbMath1015.68082OpenAlexW2033319692MaRDI QIDQ2784485

Luc Longpré, Harry Buhrman

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

Kolmogorov complexityresource bounded measurecompressibility

Mathematics Subject Classification ID

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

Related Items (4)

Sub-computable Bounded Pseudorandomness ⋮ Comparing reductions to NP-complete sets ⋮ Dimension is compression ⋮ On the Polynomial Depth of Various Sets of Random Strings

This page was built for publication: Compressibility and Resource Bounded Measure