On the Polynomial Depth of Various Sets of Random Strings

DOI10.1007/978-3-642-20877-5_50zbMATH Open1331.68118arXiv1012.3548OpenAlexW2568939953MaRDI QIDQ3010430FDOQ3010430

Authors: Philippe Moser 

Publication date: 1 July 2011

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)