The intractability of computing the Hamming distance

DOI10.1016/j.tcs.2005.02.002zbMath1078.68044OpenAlexW2072141295MaRDI QIDQ557834

Bodo Manthey, K. Ruediger Reischuk

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.02.002

zbMATH Keywords

computational complexityHamming distanceinapproximabilityedit distanceparametrized complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Information, possible worlds and the cooptation of scepticism ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Approximating the minimum maximal independence number
• A faster algorithm computing string edit distances
• A survey of multiple sequence comparison methods
• The complexity of computing maximal word functions
• How hard is computing the edit distance?
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Parity, circuits, and the polynomial-time hierarchy
• A sublinear algorithm for weakly approximating edit distance
• A linear space algorithm for computing maximal common subsequences
• On the Tape Complexity of Deterministic Context-Free Languages
• Algorithms on Strings, Trees and Sequences
• On the Amount of Nondeterminism and the Power of Verifying
• Error Detecting and Error Correcting Codes
• Syntax-directed least-errors analysis for context-free languages
• Fixed-Parameter Tractability and Completeness I: Basic Results
• The complexity of error-correcting codes
• Algorithms and Computation
• An error-correcting parse algorithm
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• A Minimum Distance Error-Correcting Parser for Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item