Moser, Philippe (2013) On the polynomial depth of various sets of random strings. Theoretical Computer Science, 477. pp. 96-108. ISSN 0304-3975

Preview

Download (312kB) | Preview

Abstract

We introduce a general framework for defining the depth of an infinite binary sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in computability/complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions. We use our framework to define 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. 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.

Item Type:	Article
Additional Information:	This is the preprint version of the published article, which is available at DOI: 10.1016/j.tcs.2012.10.045
Keywords:	Logical depth; Polynomial depth; Kolmogorov complexity; Levin complexity;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	6525
Identification Number:	https://doi.org/10.1016/j.tcs.2012.10.045
Depositing User:	Philippe Moser
Date Deposited:	04 Nov 2015 14:47
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier
Refereed:	Yes
URI:	http://www.sciencedirect.com
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads