Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ⊆ {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 ⊆ {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 ⊆ {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 ⊆ {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.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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)).

share|improve this answer
    
Hi Kolia, thanks very much! As it happens, I just learned of your paper with Vitanyi a couple weeks ago, and had revisited this question intending to post an update to it, explaining that you and Vitanyi had "essentially" answered it! –  Scott Aaronson Mar 20 '13 at 19:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.