# On the k-Hamming and k-Edit Distances

arXiv: https://arxiv.org/abs/2306.09144 · HTML: https://mlsanity.com/paper/2306.09144/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 3 of 3)

- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Adaptive Computation of the Swap-Insert Correction Distance](https://mlsanity.com/paper/1504.07298/) (2015)
- [Checking whether a word is Hamming-isometric in linear time](https://mlsanity.com/paper/2106.10541/) (2021)

## Abstract (arXiv)

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≥ 2 the DECIS-k-Hamming problem is mathbbP-SPACE-complete and the DECIS-k-Edit problem is NEXPTIME-complete.