The intractability of computing the Hamming distance

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.