Return to Question

Given an n-bit string x, recall that K(x), the Kolmogorov complexity of x, is the length in bits of the shortest program p (in some fixed universal programming language) such that p()=x: that is, p halts and outputs x when given a blank input. Given a set S ⊆ {0,1}ⁿ, one can also define K(S) to be the length in bits of the shortest program that outputs the 2ⁿ-bit characteristic sequence of x. Finally, one can define K(x|S) to be the length in bits of the shortest program p such that p(S)=x: that is, p halts and outputs x when fed the characteristic sequence of S as input.

Given an n-bit string x, recall that K(x), the Kolmogorov complexity of x, is the length in bits of the shortest program p (in some fixed universal programming language) such that p()=x: that is, p halts and outputs x when given a blank input. Given a set S ⊆ {0,1}ⁿ, one can also define K(S) to be the length in bits of the shortest program that outputs the 2ⁿ-bit characteristic sequence of S. Finally, one can define K(x|S) to be the length in bits of the shortest program p such that p(S)=x: that is, p halts and outputs x when fed the characteristic sequence of S as input.

Update: Sorry, just minutes after writing this post, I think I see the answer to one direction of my problem! Consider the "absolutely non-random objects" x discussed above. These objects satisfy K(x) ≥ NSoph_c(x) ≥ n-O(log n). But precisely because their Kolmogorov complexity is so large, they should also satisfy CSoph(x)=O(log n), achieved by setting S={0,1}ⁿ. On the other hand, I still don't know whether CSoph(x) can ever be larger than NSoph_c(x) (only that, if so, it's never more than a factor of 2 larger).

Update: Sorry, just minutes after writing this post, I think I see the answer to one direction of my problem! Consider the "absolutely non-random objects" x discussed above. These objects satisfy K(x) ≥ NSoph_c(x) ≥ n-O(log n). But precisely because their Kolmogorov complexity is so large, they should also satisfy CSoph(x)=O(log n), achieved by setting S={0,1}ⁿ. On the other hand, I still don't know whether CSoph(x) can ever be larger than NSoph_c(x) (only that, if so, it's never more than a factor of 2 larger). And I'd still be extremely interested if anyone could answer that question.

Update: Sorry, just minutes after writing this post, I think I see the answer to one direction of my problem! Consider the "absolutely non-random objects" x discussed above. These objects satisfy K(x) ≥ NSoph_c(x) ≥ n-O(log n). But precisely because their Kolmogorov complexity is so large, they should also satisfy CSoph(x)=O(log n), achieved by setting S={0,1}ⁿ. On the other hand, I still don't know whether CSoph(x) can ever be larger than NSoph_c(x) (only that, if so, it's never more than a factor of 2 larger).