On the Optimal Compression of Sets in PSPACE
From MaRDI portal
Publication:3088270
DOI10.1007/978-3-642-22953-4_6zbMath1342.68140arXiv1104.2816MaRDI QIDQ3088270
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.2816
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization, On extracting space-bounded Kolmogorov complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Low-depth witnesses are easy to find
- Language compression and pseudorandom generators
- Hardness vs randomness
- Resource bounded symmetry of information revisited
- Resource-Bounded Kolmogorov Complexity Revisited
- Kolmogorov Complexity in Randomness Extraction.
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
- Randomness Buys Depth for Approximate Counting