Computer Science – Computational Complexity
Scientific paper
2012-02-29
Computer Science
Computational Complexity
10 pages, 1 figure
Scientific paper
Peter Gacs showed [1] that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., C(C(x)|x) \geq log n - log log n - O(1). Following Elena Kalinina [3], we provide a game-theoretic proof of this result; modifying her argument, we get a better (and tight) bound log n - O(1). We also show the same bound for prefix-free complexity. Robert Solovay's showed [10] that infinitely many strings x have maximal plain complexity but not maximal prefix-free complexity (among the strings of the same length); i.e. for some c and infinitely many x: |x| - C(x) \leq c and |x| + K(|x|) - K (x) \geq log log |x| - c log log log |x|. Using the result above, we provide a short proof of Solovay's result. We also generalize it by showing that for some c and for all n there are strings x of length n with n-C(x) \leq c, and n + K(n) - K(x) \geq K(K(n)|n) - 3 K(K(K(n)|n) |n) - c. This is very close to the upperbound K (K (n)|n) + O(1) proved by Solovay.
No associations
LandOfFree
Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity 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 Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345236