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:

  1. It's sufficient to enumerate a set $S'$ such that $S \subseteq S' \subseteq \{0...n-1\}$, of size at most $\delta n$.
  2. Instead of an enumeration, I want a machine which is given $i$ and outputs the $i$-th element in $S'$.
  3. 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.


  • 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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.