## Computing Simultaneous Hamming Neighborhood for a Set of Strings

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 1 Answer

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 s1,…,sn∈{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

-
Hello Tsuyoshi, Thank you for that reference its useful. However I'm interested in the complexity when $k$ is a fixed constant. Thank you, Vamsi. – Vamsik Jul 18 2011 at 23:53
@Vamsik: If k is fixed, then it is straightforward to check all k-letter strings in poly(n) time because, as long as every letter in Σ appears in some string s_i, there are only |Σ|^k≤(kn)^k=poly(n) strings of length k. The case where Σ contains unused letters can be also handled easily. – Tsuyoshi Ito Jul 19 2011 at 0:41
@Tsuyoshi: $\Sigma$ is part of input, so any bivariate polynomial in $n$ and $\Sigma$ would be efficient. On the other hand if $\Sigma$ were to be constant I'm wondering if exists is an $O(|N_{\alpha}|)$ algorithm. – Vamsik Jul 19 2011 at 0:44
@Vamsik: If you fix k and you are fine with a polynomial in n and |Σ|, then check all the k-letter strings. There are |Σ|^k = poly(|Σ|) strings, and each string can be tested in poly(n) time for membership in N_α, which means that this algorithm runs in poly(n,|Σ|) time. – Tsuyoshi Ito Jul 19 2011 at 0:49

1
@Vamsik: (1) In that case, it is trivially impossible because you have to distinguish between the case where N_α is empty and the case where |N_α|≤100 (say) in a constant time, in which you cannot even read the whole input. (2) Even if you change the question again, I will no longer try to answer. I cannot keep chasing the moving target. – Tsuyoshi Ito Jul 19 2011 at 2:43
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9177318215370178, "perplexity_flag": "middle"}