<p>One possible measure of the &quot;complexity&quot; of a set of strings is the size of the minimal DFA that accepts exactly those strings (and no others).  I can't tell whether this has the properties you are looking for.</p>
<hr />
<p>See also <a href="https://en.wikipedia.org/wiki/Separating_words_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Separating_words_problem</a>.</p>

CC BY-SA 4.0
2024-09-05T09:29:00.340Z
I guess DFA could be here replaced by any other model of computation, such as Turing machines.
Reijo Jaakkola
CC BY-SA 4.0
2024-09-04T07:34:00.413Z
2024-09-04T07:34:00.413Z
D.W.
<p>Inspired partly by Scott Aaronson's post about <a href="https://scottaaronson.blog/?p=762" rel="nofollow noreferrer">the first law of complexodynamics</a>, I've been thinking lately about how to quantify the &quot;interesting&quot; or &quot;structured&quot; 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.</p>
<p>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 &quot;generic&quot; 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.</p>
<p>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 <em>n</em>-bit strings. Now consider a Boolean circuit with <em>n</em> inputs and one output, which discriminates members of this set from all other <em>n</em>-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.</p>
<p>To explain the intuition and meaning behind this definition, consider that the most &quot;obvious&quot; 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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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 &quot;flat&quot; - if not, that would mess up my whole approach.</p>
<p>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!</p>

CC BY-SA 4.0
2024-09-04T06:49:41.307Z
Can you [edit] your question to expand on what you mean by ``"interesting" or "structured" complexity''?
D.W.
CC BY-SA 4.0
2024-09-04T18:31:02.737Z
@D.W. I think the issue lies in the difficulty of defining it. It's similar to asking what it means for an individual string to be random before Kolmogorov complexity was invented. You can say it "looks" random but there isn't a good definition. The best definition I can give is a string which has structure, but the structure is very 'complicated'. E.g. a string containing the binary expansion of the first 8 Fibonacci numbers is more interesting than a string '10101010...' of the same length. It's also not random because there is a pattern, it just might not be obvious at first glance.
CyborgOctopus
CC BY-SA 4.0
2024-09-04T20:14:08.293Z
Even if you can't define it, it would help if you could give anything to narrow it down.  Are there any criteria you will use to evaluate proposed answers?  Can you give some examples of what you want the definition to be for certain types of strings?  Maybe some extreme cases, like a random bitstring of length $n$; the all-zeros bitstring; the output of a PRNG on a fixed small seed.
D.W.
<cc.complexity-theory><it.information-theory><kolmogorov-complexity>
A potentially novel complexity measure for sets of strings
CyborgOctopus
# A potentially novel complexity measure for sets of strings

(Asked by: username_0 on 2024-09-03)

Inspired partly by Scott Aaronson's post about [the first law of complexodynamics](https://scottaaronson.blog/?p=762), 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!

**Tags:** cc.complexity-theory, it.information-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: Can you [edit] your question to expand on what you mean by ``"interesting" or "structured" complexity''?  
> **username_0**: @D.W. I think the issue lies in the difficulty of defining it. It's similar to asking what it means for an individual string to be random before Kolmogorov complexity was invented. You can say it "looks" random but there isn't a good definition. The best definition I can give is a string which has structure, but the structure is very 'complicated'. E.g. a string containing the binary expansion of the first 8 Fibonacci numbers is more interesting than a string '10101010...' of the same length. It's also not random because there is a pattern, it just might not be obvious at first glance.  
> **username_1**: Even if you can't define it, it would help if you could give anything to narrow it down.  Are there any criteria you will use to evaluate proposed answers?  Can you give some examples of what you want the definition to be for certain types of strings?  Maybe some extreme cases, like a random bitstring of length $n$; the all-zeros bitstring; the output of a PRNG on a fixed small seed.  

---

## 1 answers

### Answer by username_1 on 2024-09-04. Score: 3

One possible measure of the "complexity" of a set of strings is the size of the minimal DFA that accepts exactly those strings (and no others). I can't tell whether this has the properties you are looking for.

---

See also <https://en.wikipedia.org/wiki/Separating_words_problem>.

> **Comments:**
> **username_2**: I guess DFA could be here replaced by any other model of computation, such as Turing machines.  

---

