Consider the following problem:
Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.
Output: The encoding of some kind of automaton (say, a Turing machine) which enumerates this set.
If you want the shortest machine, then this is a witness variant of determining the Kolmogorov complexity of the input. This is intractable of course.
But now suppose I make the following changes/relaxations to the problem:
- It's sufficient to enumerate a set $S'$ such that $S \subseteq S' \subseteq \{0...n-1\}$, of size at most $\delta n$.
- Instead of an enumeration, I want a machine which is given $i$ and outputs the $i$-th element in $S'$.
- I don't really need the smallest machine. I only need its size to be independent on $n$, and I want it to be fast - taking $T(n)$ time.
So my parameters are $\delta$ and $T(n)$; I need to devise an algorithm which gives a good tradeoff between them, as a factor of $n$, in the worst-case (i.e. for all values of $S$). And - no asymptotics for that tradeoff! No monstrous constants hidden in $O(\cdot)$ notations, this needs to work in the "real" world.
Now, of course I don't expect people here to solve this problem for me. What I was hoping is that this, or similar, problems have been studied in the TCS community, enough for people to provide suggested directions/pointers/inspirations for this.
Notes:
- A variant of the above which is also of interest is when $S'$ can also discard some elements of $S$, say, $\varepsilon |S|$ of them.
- If you want some motivation, think: "Dictionary-like compression scheme selection mechanism".
