The intractability of computing the Hamming distance (Q557834)

The Hamming distance of a string \(x\) to a language \(L\) is the minimum Hamming distance of \(x\) to any string in \(L\). The paper presents a number of results on the complexity of computing the Hamming distance. Namely, there exist a language in AC\(^0\) such that both Hamming distance and edit distance to this language are hard to approximate. Also for every \(t \in N\) there is a language in AC\(^0\) for which computing the Hamming distance is W\([t]\)-hard, and there is a language in P for which the same problem is WP-hard. Then approximation-ratio preserving reductions from the problem of computing the Hamming distance to the problem of computing the edit distance and vice versa are given to show that these problems are in some sense equivalent. Finally, HamP -- the class of languages to which the Hamming distance can be efficiently computed -- is introduced and some of its properties are studied. However, its characterization in terms of automata or formal languages remains an open problem and some evidence is given that such characterization might be difficult.