Inspired partly by Scott Aaronson's post about the first law of complexodynamics, I've been thinking lately about how to quantify the "interesting" or "structured" complexity of a string. Kolmogorov complexity is not adequate for this purpose since it is highest for 'random' (totally unstructured) strings which, intuitively, are not very interesting at all.
I know there are approaches which attempt to do this, such as sophistication and computational depth. Recently I had an idea that I think in a way combines the approaches. As far as I understand, sophistication tries to measure the amount of information required to specify a set of which a given string is a "generic" member. Computational depth on the other hand tries to measure the amount of time required by a Turing machine (or depth of a Boolean circuit) to compute a string from some short description.
I have thought of a complexity measure for sets of strings, which I'm hopeful could somehow be extended to individual strings. Consider a set of n-bit strings. Now consider a Boolean circuit with n inputs and one output, which discriminates members of this set from all other n-bit strings, i.e. it outputs a 1 for members of the set and 0 for all other inputs. The complexity of the set is the depth of the smallest such discriminating circuit (if there are multiple smallest, then the depth of the shallowest one). In case it's unclear I mean smallest in the sense of fewest vertices.
To explain the intuition and meaning behind this definition, consider that the most "obvious" way of discriminating any given set would be just building a lookup table containing all of its elements. Then the circuit matches its input against everything in the lookup table, and if there's no match it's rejected.
I would imagine that a circuit embodying this lookup table should be roughly the same size as the set. Since clearly any set can be discriminated using a lookup table, its size also bounds the complexity. Any circuit with a higher depth than the size of the lookup table could not be a candidate for the smallest discriminator, since the lookup table is smaller.
In order to do better than the lookup table (produce a smaller discriminator), some type of structure in the set must be exploited. It seems to me that the more complex this structure, the greater depth of the circuit will be needed. There is always a tradeoff since this greater depth must still make the circuit smaller. Therefore the shortest discriminator seems to optimally exploit all the structure in the set, and its depth measures how complex that structure this.
This complexity measure is similar to sophistication by using the concept of the complexity of a set of strings, and similar to computational depth by using the concept of depth of a Boolean circuit.
I believe it also has the desirable property alluded to in Aaronson's blog post that it is low both for sets containing purely strings of low Kolmogorov complexity, as well as for sets containing purely strings of very high Kolmogorov complexity (random strings). In the first case, the patterns are very simple so it shouldn't require a very deep circuit to discriminate them. In the second case, there are no patterns so the lookup table approach should be best. I'm assuming a lookup table circuit could be very "flat" - if not, that would mess up my whole approach.
I'd be very interested in hearing feedback on this idea. I'm not an expert in this field and my idea could be totally off base. Has any similar work been done? Did I just reinvent something that has already been considered? Is it just nonsense? Thanks for any insights!
