On Time-Bounded Incompressibility of Compressible Strings and Sequences

Details On Time-Bounded Incompressibility of Compressible Strings and Sequences On Time-Bounded Incompressibility of Compressible Strings and Sequences

2008-09-17

arxiv.org/abs/0809.2965v4

Computer Science

Computational Complexity

9 pages, LaTeX, no figures, submitted to Information Processing Letters. Changed and added a Barzdins-like lemma for infinite

Scientific paper

For every total recursive time bound $t$, a constant fraction of all compressible (low Kolmogorov complexity) strings is $t$-bounded incompressible (high time-bounded Kolmogorov complexity); there are uncountably many infinite sequences of which every initial segment of length $n$ is compressible to $\log n$ yet $t$-bounded incompressible below ${1/4}n - \log n$; and there are countable infinitely many recursive infinite sequence of which every initial segment is similarly $t$-bounded incompressible. These results are related to, but different from, Barzdins's lemma.

Affiliated with

Also associated with

No associations

Rating

On Time-Bounded Incompressibility of Compressible Strings and Sequences 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 On Time-Bounded Incompressibility of Compressible Strings and Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Time-Bounded Incompressibility of Compressible Strings and Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661859