Computing Simultaneous Hamming Neighborhood for a Set of Strings - MathOverflow

Computing Simultaneous Hamming Neighborhood for a Set of Strings

2011-07-18T17:45:40Z

Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming neighborhood is defined as $N_{\alpha} = \lbrace s' | h(s',s_j) \leq \alpha, \forall s_j \in S , s' \in \Sigma^k \rbrace$, $1\leq \alpha \leq k$.

I would like to know if this problem (i.e. computing $N_{\alpha}$ efficiently) has been considered earlier ? -- By efficiently I mean the running time of the algorithm should be something like $O(|N_{\alpha}|)$, when $|N_{\alpha}|$ is much larger than $n$.

Thank you very much for your help.

Answer by Tsuyoshi Ito for Computing Simultaneous Hamming Neighborhood for a Set of Strings

2011-07-18T23:34:34Z

I assume that you require the running time of an algorithm to be polynomial also in k. Then this is impossible even with the binary alphabet unless P=NP by the result by Frances and Litman [FL97].

Consider the easier task of deciding, given k-bit strings s₁,…,s_n∈{0,1}^k and an integer α, whether N_α contains any element or not. This problem is equivalent to what is called the Minimum Radius problem in [FL97], where it is proved to be NP-complete.

[FL97] M. Frances and A. Litman. On covering problems of codes. Theory of Computing Systems, 30(2):113–119, March 1997. http://dx.doi.org/10.1007/BF02679443