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 that you have read and understand our privacy policy and code of conduct.