Everywhere complex sequences and the probabilistic method

DOI10.4230/LIPICS.STACS.2011.464MaRDI QIDQ3113711zbMATH OpenOpenAlexFDO

Authors A. Yu. Rumyantsev

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/1009.3649, http://subs.emis.de/LIPIcs/frontdoor_65fe.html

zbMATH Keywords

everywhere complex sequencesKolmogorov complexityMedvedev reducibilityMuchnik reducibilityrandomized algorithms

Mathematics Subject Classification ID

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

Abstract: The main subject of the paper is everywhere complex sequences. An everywhere complex sequence is a sequence that does not contain substrings of Kolmogorov complexity less than $alphan-O(1)$ where $n$ is the length of substring and $alpha$ is a constant between 0 and 1. First, we prove that no randomized algorithm can produce everywhere complex sequence with positive probability. On the other hand, for weaker notions of everywhere complex sequences the situation is different. For example, there is a probabilistic algorithm that produces (with probability~1) sequences whose substrings of length $n$ have complexity $sqrtn-O(1)$. Finally, one may replace the complexity of a substring (in the definition of everywhere complex sequence) by its conditional complexity when the position is given. This gives a stronger notion of everywhere complex sequence, and no randomized algorighm can produce (with positive probability) such a sequence even if $alphan$ is replaced by $sqrtn$, $lo{g}^{\ast }n$ or any other monotone unbounded computable function.

Recommendations

• scientific article; zbMATH DE number 4043283
• scientific article; zbMATH DE number 270263
• Statistical properties of finite sequences with high Kolmogorov complexity
• Almost everywhere high nonuniform complexity
• scientific article; zbMATH DE number 3890727

Cited in

(6)

• On the Ehrenfeucht-Mycielski sequence
• Construction of sequences of zeros and ones with complex finite sequences
• Constraints placed on random sequences by their compressibility
• Diagonally non-computable functions and fireworks
• Shift-complex sequences
• Deep _1⁰ classes

This page was built for publication: Everywhere complex sequences and the probabilistic method

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