The intractability of computing the Hamming distance

Manthey, Bodo and Reischuk, Rüdiger (2005) The intractability of computing the Hamming distance. Theoretical Computer Science, 337 (1-3). pp. 331-346. ISSN 0304-3975

PDF
Restricted to UT campus only: Request a copy
232Kb

Abstract:	Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined. First, we prove that there is a language in $AC^0$ such that both Hamming and edit distance to this language are hard to approximate; they cannot be approximated with factor $O(n^{(1/3)-ε})$ , for any ε>0, unless P=NP (n denotes the length of the input string). Second, we show the parameterized intractability of computing the Hamming distance. We prove that for every t∈N there exists a language in $AC^0$ for which computing the Hamming distance is W[t]-hard. Moreover, there is a language in P for which computing the Hamming distance is WP-hard. Then we show that the problems of computing the Hamming distance and of computing the edit distance are in some sense equivalent by presenting approximation ratio preserving reductions from the former to the latter and vice versa. Finally, we define HamP to be the class of languages to which the Hamming distance can efficiently, i.e. in polynomial time, be computed. We show some properties of the class HamP. On the other hand, we give evidence that a characterization in terms of automata or formal languages might be difficult.
Item Type:	Article
Copyright:	© 2005 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79423
Official URL:	http://dx.doi.org/10.1016/j.tcs.2005.02.002
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page