3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.