On the polynomial depth of various sets of random strings

DOI10.1016/J.TCS.2012.10.045zbMath1283.68177OpenAlexW2108502379MaRDI QIDQ1945946

Philippe Moser

Publication date: 17 April 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.10.045

zbMATH Keywords

Kolmogorov complexitylogical depthLevin complexitypolynomial depth

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithms on strings (68W32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Lowness and logical depth ⋮ Depth, Highness and DNR Degrees ⋮ Pushdown and Lempel-Ziv depth ⋮ Limit-depth and DNR degrees ⋮ On the Difference Between Finite-State and Pushdown Depth ⋮ Searching for shortest and least programs ⋮ Polylog depth, highness and lowness for E ⋮ Randomness below complete theories of arithmetic

This page was built for publication: On the polynomial depth of various sets of random strings