Resource-Bounded Kolmogorov Complexity Revisited
From MaRDI portal
Publication:2784486
DOI10.1137/S009753979834388XzbMath1017.68061MaRDI QIDQ2784486
Sophie Laplante, Harry Buhrman, Lance J. Fortnow
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
NL-printable sets and nondeterministic Kolmogorov complexity, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Generation Complexity Versus Distinction Complexity, Variations on Muchnik's conditional complexity theorem, A linearly computable measure of string complexity, Short lists for shortest descriptions in short time, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, An incompressibility theorem for automatic complexity, Short lists with short programs in short time, Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization, Avoiding simplicity is complex, NL-printable sets and Nondeterministic Kolmogorov Complexity, Proof systems that take advice, Closure and nonclosure properties of the classes of compressible and rankable sets, Nondeterministic Instance Complexity and Proof Systems with Advice, On algorithmic statistics for space-bounded algorithms, On the Optimal Compression of Sets in PSPACE, Some structural properties of SAT, Resource bounded symmetry of information revisited, On optimal language compression for sets in PSPACE/poly
