Paper ID: 2306.09144

On the $k$-Hamming and $k$-Edit Distances

Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi, Matteo Spezialetti

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.

Submitted: Jun 15, 2023