License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.464
URN: urn:nbn:de:0030-drops-30353
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3035/
Go to the corresponding LIPIcs Volume Portal

Rumyantsev, Andrey Yu.

Everywhere complex sequences and the probabilistic method

pdf-format:
43.pdf (0.5 MB)

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 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.

BibTeX - Entry

@InProceedings{rumyantsev:LIPIcs:2011:3035,
  author =	{Andrey Yu. Rumyantsev},
  title =	{{Everywhere complex sequences and the probabilistic method}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{464--471},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3035},
  URN =		{urn:nbn:de:0030-drops-30353},
  doi =		{10.4230/LIPIcs.STACS.2011.464},
  annote =	{Keywords: Kolmogorov complexity, everywhere complex sequences, randomized algorithms, Medvedev reducibility, Muchnik reducibility}
}

Keywords: Kolmogorov complexity, everywhere complex sequences, randomized algorithms, Medvedev reducibility, Muchnik reducibility
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI