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.
What is the problem of finding a largest subset of smallest Kolmogorov complexity?
cc.complexity theory;it.information theory;kolmogorov complexity