# What is the problem of finding a largest subset of smallest Kolmogorov complexity?

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.

• 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 Aug 7 '15 at 18:50
• The complexity measure could be time-bounded, I don't have any specific requirements about that. – argentpepper Aug 7 '15 at 19:21
• Then I think that you should pose your question using some time-bounded complexity measure and not Kolmogorov complexity. – domotorp Aug 7 '15 at 19:46
• 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 Oct 5 '16 at 10:39
• @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 Oct 5 '16 at 21:13