On the Polynomial Depth of Various Sets of Random Strings

DOI10.1007/978-3-642-20877-5_50MaRDI QIDQ3010430zbMATH OpenOpenAlexFDO

Authors 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, http://eprints.maynoothuniversity.ie/6525/1/PM-Polynomial.pdf

Mathematics Subject Classification ID

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

Abstract: This paper proposes new notions of polynomial depth (called monotone poly depth), based on a polynomial version of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions i.e., both trivial and random sequences are not monotone poly deep, monotone poly depth satisfies the slow growth law i.e., no simple process can transform a non deep sequence into a deep one, and monotone poly deep sequences exist (unconditionally). We give two natural examples of deep sets, by showing that both the set of Levin-random strings and the set of Kolmogorov random strings are monotone poly deep.

Recommendations

• On the polynomial depth of various sets of random strings
• On the complexity of random strings
• On the Topological Size of Sets of Random Strings
• On nonadaptive reductions to the set of random strings and its dense subsets
• Lower bounds for reducibility to the Kolmogorov random strings
• Polynomial configurations in subsets of random and pseudo-random sets
• On the computational power of random strings
• scientific article; zbMATH DE number 1336330

Cites work

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

Cited in

(6)

• Low-depth witnesses are easy to find
• Depth as randomness deficiency
• Random strings and truth-table degrees of Turing complete c.e. sets
• Polylog depth, highness and lowness for E
• On the polynomial depth of various sets of random strings
• Computational depth: Concept and applications

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

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