Computing Simultaneous Hamming Neighborhood for a Set of Strings - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:54:59Z http://mathoverflow.net/feeds/question/70651 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70651/computing-simultaneous-hamming-neighborhood-for-a-set-of-strings Computing Simultaneous Hamming Neighborhood for a Set of Strings Vamsik 2011-07-18T17:45:40Z 2011-07-19T03:44:36Z <p>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$. </p> <p>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$. </p> <p>Thank you very much for your help.</p> http://mathoverflow.net/questions/70651/computing-simultaneous-hamming-neighborhood-for-a-set-of-strings/70687#70687 Answer by Tsuyoshi Ito for Computing Simultaneous Hamming Neighborhood for a Set of Strings Tsuyoshi Ito 2011-07-18T23:34:34Z 2011-07-18T23:34:34Z <p>I assume that you require the running time of an algorithm to be polynomial also in <i>k</i>. Then this is impossible even with the binary alphabet unless P=NP by the result by Frances and Litman [FL97].</p> <p>Consider the easier task of deciding, given <i>k</i>-bit strings <i>s</i><sub>1</sub>,…,<i>s</i><sub><i>n</i></sub>∈{0,1}<sup><i>k</i></sup> and an integer <i>α</i>, whether <i>N</i><sub><i>α</i></sub> 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.</p> <p>[FL97] M. Frances and A. Litman. On covering problems of codes. <em>Theory of Computing Systems</em>, 30(2):113–119, March 1997. <a href="http://dx.doi.org/10.1007/BF02679443" rel="nofollow">http://dx.doi.org/10.1007/BF02679443</a></p>