Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
    
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 '11 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 '11 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 '11 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 '11 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 '11 at 2:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.