<p>What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting and would like to know about this more abstract problem. In terms of Kolmogorov complexity, this would be the following decision problem.</p>

<blockquote>
  <p>Given: a finite set of binary strings <em>S</em> and positive integers <em>c</em> and <em>d</em>.</p>
  
  <p>Question: is there a subset <em>S'</em> of <em>S</em> such that |<em>S'</em>| is at least <em>c</em> and the resource-bounded Kolmogorov complexity of <em>S'</em> is at most <em>d</em>?</p>
</blockquote>

<p><em>Edit:</em> consider the complexity measure to be one of the resource-bounded Kolmogorov complexity measures (for example, the length of the shortest program that outputs a given string, with an additive penalty of the logarithm of the running time of the program) to make the problem computable, as suggested in the comments.</p>

CC BY-SA 3.0
2015-08-07T18:50:24.350Z
Unless I'm missing something, it is undecidable; given a string $s$ you would be able to calculate its Kolmogorov complexity simply setting $S = \{s\}, c = 1, d = |s|, |s|-1, |s|-2, ...$
Marzio De Biasi
CC BY-SA 3.0
2015-08-07T19:21:06.833Z
The complexity measure could be time-bounded, I don't have any specific requirements about that.
argentpepper
CC BY-SA 3.0
2015-08-07T19:46:31.147Z
Then I think that you should pose your question using some time-bounded complexity measure and not Kolmogorov complexity.
domotorp
CC BY-SA 3.0
2016-10-05T10:39:11.463Z
Could you specify your question? Resource-bounded Kolmogorov complexity of a set can be defined by several (natural) ways. For example you may define it as the complexity of a list of strings. However in such case $\{0,1\}^n$ will have huge complexity. Instead of this you can consider distinguishing complexity of a set...
Alexey Milovanov
CC BY-SA 3.0
2016-10-05T21:13:40.180Z
@Alexey I didn't get as far as considering the difference between the different possible definitions of "complexity of a set", I was really just asking whether this problem had been studied before, for any appropriate definition. But it seems not.
argentpepper
CC BY-SA 3.0
2016-10-05T23:10:08.623Z
Assume that $S = \{x\}$. In such case the problem is to estimate the resource-bounded Kolmogorov complexity of $x$. Let us consider polynomial-time bounded. Then it is not difficult to show that there are no a polynomial time algorithm that estimates polynomial-time bounded Kolmogorov complexity if Cryptographically secure pseudorandom number generators exist (= one-way functions exist).
Alexey Milovanov
CC BY-SA 3.0
2016-10-05T23:16:04.907Z
If you consider a set like a list then your problem belongs to $\mathsf{NP}$ for polynomial-time bounded Kolmogorov complexity.
Alexey Milovanov
<cc.complexity-theory><it.information-theory><kolmogorov-complexity>
What is the problem of finding a largest subset of smallest Kolmogorov complexity?
argentpepper
# What is the problem of finding a largest subset of smallest Kolmogorov complexity?

(Asked by: username_0 on 2015-08-07)

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting and would like to know about this more abstract problem. In terms of Kolmogorov complexity, this would be the following decision problem.

> Given: a finite set of binary strings *S* and positive integers *c* and *d*.
>
> Question: is there a subset *S'* of *S* such that |*S'*| is at least *c* and the resource-bounded Kolmogorov complexity of *S'* is at most *d*?

*Edit:* consider the complexity measure to be one of the resource-bounded Kolmogorov complexity measures (for example, the length of the shortest program that outputs a given string, with an additive penalty of the logarithm of the running time of the program) to make the problem computable, as suggested in the comments.

**Tags:** cc.complexity-theory, it.information-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: Unless I'm missing something, it is undecidable; given a string $s$ you would be able to calculate its Kolmogorov complexity simply setting $S = \{s\}, c = 1, d = |s|, |s|-1, |s|-2, ...$  
> **username_0**: The complexity measure could be time-bounded, I don't have any specific requirements about that.  
> **username_2**: Then I think that you should pose your question using some time-bounded complexity measure and not Kolmogorov complexity.  
> **username_3**: Could you specify your question? Resource-bounded Kolmogorov complexity of a set can be defined by several (natural) ways. For example you may define it as the complexity of a list of strings. However in such case $\{0,1\}^n$ will have huge complexity. Instead of this you can consider distinguishing complexity of a set...  
> **username_0**: @Alexey I didn't get as far as considering the difference between the different possible definitions of "complexity of a set", I was really just asking whether this problem had been studied before, for any appropriate definition. But it seems not.  
> **username_3**: Assume that $S = \{x\}$. In such case the problem is to estimate the resource-bounded Kolmogorov complexity of $x$. Let us consider polynomial-time bounded. Then it is not difficult to show that there are no a polynomial time algorithm that estimates polynomial-time bounded Kolmogorov complexity if Cryptographically secure pseudorandom number generators exist (= one-way functions exist).  
> **username_3**: If you consider a set like a list then your problem belongs to $\mathsf{NP}$ for polynomial-time bounded Kolmogorov complexity.  

---

## 0 answers

