# Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $$\Sigma$$ be the alphabet, $$0 be an integer and let $$\Sigma^n$$ denote the set of all strings of length $$n$$ over the alphabet. The task is to find the minimum $$m$$ such that there exist strings $$S=\{s_1, \dots, s_m\}\subseteq \Sigma^n$$ that satisfy: $$\forall x\in \Sigma^n\;\; \exists y\in S\colon ED(x,y)\le R$$ In other words, we want to minimize $$|S|$$, such that any string of length $$n$$ can be constructed from them with at most $$R$$ edit operation.

Let $$S^\star$$ denote one optimal solution. My guess is that an algorithm computing an optimal solution is not efficient, and likely to grow as a function of $$|\Sigma|^n$$. My question is, is it possible to compute an approximate solution, say satisfying $$|S|\le 2|S^\star|$$, in time polynomial in input size $$\mathrm{Poly}(|\Sigma|,m,n)$$?

• Interesting question. One thing that might make this tricky is that there's certainly a P/poly algorithm for this (the advice for $n$ records the optimal $m$), and it might be a bit delicate to distinguish between P vs P/poly. It might be that this is more of a question about math than about algorithms (i.e., maybe you need a construction of such a set $S$ that you can prove 2-optimal, and the challenge is in identifying/proving the construction rather than in finding an algorithm to compute it.)
– D.W.
Jan 17 '20 at 19:57