On the Polynomial Depth of Various Sets of Random Strings

DOI10.1007/978-3-642-20877-5_50zbMath1331.68118arXiv1012.3548OpenAlexW2568939953MaRDI QIDQ3010430

Philippe Moser

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.3548

Mathematics Subject Classification ID

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

Cites Work

• Martingale families and dimension in P
• Computational depth and reducibility
• Recursive computational depth.
• Computational depth: Concept and applications
• What can be efficiently reduced to the Kolmogorov-random strings?
• Compressibility and Resource Bounded Measure
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Randomness conservation inequalities; information and independence in mathematical theories
• STACS 2004
• Feasible Depth
• Power from Random Strings

This page was built for publication: On the Polynomial Depth of Various Sets of Random Strings