On the $k$-Hamming and $k$-Edit Distances
Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi, Matteo Spezialetti
arXiv:2306.09144v12 citationsh-index: 26
Originality Incremental advance
AI Analysis
This provides foundational complexity results for generalized string distances, which is incremental but important for theoretical computer science and algorithm design.
The paper tackles the computational complexity of weighted k-Hamming and k-Edit distances, proving that DECIS-k-Hamming is P-SPACE-complete and DECIS-k-Edit is NEXPTIME-complete for any k≥2.
In this paper we consider the weighted $k$-Hamming and $k$-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any $k\geq 2$ the DECIS-$k$-Hamming problem is $\mathbb{P}$-SPACE-complete and the DECIS-$k$-Edit problem is NEXPTIME-complete.