Everywhere complex sequences and probabilistic method

Details Everywhere complex sequences and probabilistic method Everywhere complex sequences and probabilistic method

2010-09-19

arxiv.org/abs/1009.3649v1

Mathematics

Combinatorics

Scientific paper

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 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 $\sqrt{n}-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 $\alpha n$ is replaced by $\sqrt{n}$, $\log^* n $ or any other monotone unbounded computable function.

Affiliated with

Also associated with

No associations

Rating

Everywhere complex sequences and probabilistic method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Everywhere complex sequences and probabilistic method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Everywhere complex sequences and probabilistic method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408929