2026-07-20T05:31:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3035 2024-03-06T10:33:46Z ddc:004 open_access

Everywhere complex sequences and the probabilistic method Rumyantsev, Andrey Yu. Kolmogorov complexity everywhere complex sequences randomized algorithms Medvedev reducibility Muchnik reducibility 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 alpha n-O(1) where n is the length of the substring and alpha is a constant between 0 and 1. First, we prove that no randomized algorithm can produce an 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 sqrt(n) - O(1). Finally, one may replace the complexity of a substring (in the definition of everywhere complex sequences) by its conditional complexity when the position is given. This gives a stronger notion of everywhere complex sequence, and no randomized algorithm can produce (with positive probability) such a sequence even if alpha n is replaced by sqrt(n), log*(n) or any other monotone unbounded computable function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrey Yu. Rumyantsev 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.464 urn:nbn:de:0030-drops-30353 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.464 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode