This question is about <i>sophistication</i>, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define all the needed concepts below, but for further reading, I recommend <a href="http://people.cs.uchicago.edu/~fortnow/papers/soph.pdf">this paper</a> by Antunes and Fortnow, <a href="http://www.dcc.fc.up.pt/~lfa/thesis.ps.gz">this PhD thesis</a> by Antunes, or <a href="http://homepages.cwi.nl/~paulv/papers/algorithmicstatistics.pdf">this paper</a> by Gacs, Tromp, and Vitanyi.
Given an n-bit string x, recall that K(x), the <i>Kolmogorov complexity</i> 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}<sup>n</sup>, one can also define K(S) to be the length in bits of the shortest program that outputs the 2<sup>n</sup>-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.
The "problem" with Kolmogorov complexity is that it's maximized by random strings, which are intuitively not very "complex" at all. This motivates the following alternatives to K(x):
Given an n-bit string x and a constant c>0, the oxymoronically-named <i>naïve sophistication</i> of x, or NSoph<sub>c</sub>(x), is the smallest possible value of K(S), over all sets S ⊆ {0,1}<sup>n</sup> such that x∈S and K(x|S) ≥ log<sub>2</sub>|S| - c. Intuitively, NSoph measures the minimum number of bits needed to specify a set of which x is an incompressible or Kolmogorov-random element. I call it "naïve" because it's the first measure I would think of that's sort of like Kolmogorov complexity but small for random strings (small because for random strings, one can take S={0,1}<sup>n</sup>, whence NSoph<sub>c</sub>(x)=O(1)).
Meanwhile, the <i>coarse sophistication</i> of x or CSoph(x), defined by Antunes, is the smallest possible value of 2K(S)+log<sub>2</sub>|S|-K(x), over all sets S ⊆ {0,1}<sup>n</sup> such that x∈S. Intuitively, CSoph measures the minimum number of bits needed to specify x via a "two-part code," where the first part specifies a set S containing x, the second part gives the index of x in S, and a penalty gets applied both for K(S) (the length of the first part of the code) and for K(S)+log<sub>2</sub>|S|-K(x) (the amount by which the total code length exceeds K(x)). Despite the unwieldy definition, Antunes <a href="http://www.dcc.fc.up.pt/~lfa/thesis.ps.gz">amasses evidence</a> that CSoph is in various ways the "right" measure of the non-random information in a string.
My question is now the following:
<blockquote>Let c=O(1). Is NSoph<sub>c</sub>(x), my "unsophisticated kind of sophistication," always close to CSoph(x), Antunes' "sophisticated kind of sophistication"? Or can there be a large gap between the two? If so, how large?</blockquote>
Here's what I know about this question:
<ul>
<li>CSoph(x) ≤ 2NSoph<sub>c</sub>(x)+c. To see this: let the set S minimize K(S) subject to x∈S and K(x|S) ≥ log<sub>2</sub>|S| - c. Then CSoph(x) ≤ 2K(S)+log<sub>2</sub>|S|-K(x) ≤ 2NSoph<sub>c</sub>(x)+log<sub>2</sub>|S|-K(x) ≤ 2NSoph<sub>c</sub>(x)+log<sub>2</sub>|S|-K(x|S) ≤ 2NSoph<sub>c</sub>(x)+c.
<li>NSoph<sub>c</sub>(x) <i>can</i> be about twice as large as CSoph(x). To see this: first, as observed by Antunes, if x is an n-bit string, then CSoph(x) never exceeds n/2+o(n). (For we can always achieve that bound by setting S={x} if K(x)≤n/2, or S={0,1}<sup>n</sup> if K(x)>n/2.) Second, as discussed by Gacs, Tromp, Vitanyi, it's possible to construct what Kolmogorov called "absolutely non-random objects," meaning n-bit strings x such that K(x|S) ≤ log<sub>2</sub>|S| - O(1) whenever K(S) ≤ n - clog(n). For these strings, we clearly have NSoph<sub>c</sub>(x) ≥ n-O(log n) if c=O(1). Combining now yields the result.
</ul>
As a final note, NSoph and CSoph are <i>both</i> different from the "ordinary sophistication" Soph, which is defined as follows: Soph<sub>c</sub>(x) is the smallest possible value of K(S), over all sets S ⊆ {0,1}<sup>n</sup> such that x∈S and K(S) + log<sub>2</sub>|S| ≤ K(x)+c. Intuitively, Soph<sub>c</sub>(x) measures the minimum number of bits needed for the <i>first</i> part of a near-minimal two-part code specifying the string x. One can observe the following (I'll give details on request):
<ul>
<li>NSoph<sub>c</sub>(x) ≤ Soph<sub>c</sub>(x)
<li>CSoph(x) ≤ Soph<sub>c</sub>(x)+c
<li>There exist strings x for which Soph<sub>c</sub>(x) is very large but NSoph<sub>c</sub>(x) and CSoph(x) are both very small.
</ul>