Can a string's sophistication be defined in an unsophisticated way? This question is about sophistication, 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 this paper by Antunes and Fortnow, this PhD thesis by Antunes, or this paper by Gacs, Tromp, and Vitanyi.
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 &subseteq; {0,1}n, one can also define K(S) to be the length in bits of the shortest program that outputs the 2n-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.
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 naïve sophistication of x, or NSophc(x), is the smallest possible value of K(S), over all sets S &subseteq; {0,1}n such that x∈S and K(x|S) ≥ log2|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}n, whence NSophc(x)=O(1)).
Meanwhile, the coarse sophistication of x or CSoph(x), defined by Antunes, is the smallest possible value of 2K(S)+log2|S|-K(x), over all sets S &subseteq; {0,1}n 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)+log2|S|-K(x) (the amount by which the total code length exceeds K(x)).  Despite the unwieldy definition, Antunes amasses evidence that CSoph is in various ways the "right" measure of the non-random information in a string.
My question is now the following:
Let c=O(1).  Is NSophc(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?
Here's what I know about this question:


*

*CSoph(x) ≤ 2NSophc(x)+c.  To see this: let the set S minimize K(S) subject to x∈S and K(x|S) ≥ log2|S| - c.  Then CSoph(x) ≤ 2K(S)+log2|S|-K(x) ≤ 2NSophc(x)+log2|S|-K(x) ≤ 2NSophc(x)+log2|S|-K(x|S) ≤ 2NSophc(x)+c.


*NSophc(x) can 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}n 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) ≤ log2|S| - O(1) whenever K(S) ≤ n - clog(n).  For these strings, we clearly have NSophc(x) ≥ n-O(log n) if c=O(1).  Combining now yields the result.


As a final note, NSoph and CSoph are both different from the "ordinary sophistication" Soph, which is defined as follows: Sophc(x) is the smallest possible value of K(S), over all sets S &subseteq; {0,1}n such that x∈S and K(S) + log2|S| ≤ K(x)+c.  Intuitively, Sophc(x) measures the minimum number of bits needed for the first part of a near-minimal two-part code specifying the string x.  One can observe the following (I'll give details on request):


*

*NSophc(x) ≤ Sophc(x)

*CSoph(x) ≤ Sophc(x)+c

*There exist strings x for which Sophc(x) is very large but NSophc(x) and CSoph(x) are both very small.


I'll also observe that NSophc(x), CSoph(x), and Sophc(x) are all upper-bounded by the Kolmogorov complexity K(x) (or rather, by K(x)+c).
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) ≥ NSophc(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}n.  On the other hand, I still don't know whether CSoph(x) can ever be larger than NSophc(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.
 A: Hi Scott,
are you asking whether CSoph(x) may be much more NSoph_c(x) for every constant c? This question looks strange as NSoph_c(x) increases, as c decreases. Thus the question reduces to the case c=0 (or may be you allow negative values?). Which question precisely did you have in mind? Note also that Kolmogorov complexity K(x)  itself is defined up to an additive constant term (BTW, I assume that you meant the plain complexity and not prefix one). Thus you should specify the quantifier over K(x). 
One reading of your question is the following: 
Is it true that for all c, all K and all d there is a x 
with CSoph(x) > NSoph_c(x) + d
Another reading is the following: 
Is it true that for all c there is K such that for all d there is a x 
with CSoph(x) > NSoph_c(x) + d
Kolia.
P.S. May be you will be interested also in the following result from our joint with Paul Vitanyi paper from FOCS 2002: if we allow logarithmic changes of c than soph and NSoph coincide (with logarithmic precision):
soph_{c+O(\log K(x))}(x) <  Nsoph_c(x) +O(\log K(x)).
