The intractability of computing the Hamming distance (Q557834): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jozef Vyskoč / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q17 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 2184060 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Hamming distance | |||
Property / zbMATH Keywords: Hamming distance / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
edit distance | |||
Property / zbMATH Keywords: edit distance / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inapproximability | |||
Property / zbMATH Keywords: inapproximability / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
computational complexity | |||
Property / zbMATH Keywords: computational complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
parametrized complexity | |||
Property / zbMATH Keywords: parametrized complexity / rank | |||
Normal rank |
Revision as of 15:09, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The intractability of computing the Hamming distance |
scientific article |
Statements
The intractability of computing the Hamming distance (English)
0 references
30 June 2005
0 references
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.
0 references
Hamming distance
0 references
edit distance
0 references
inapproximability
0 references
computational complexity
0 references
parametrized complexity
0 references