Złożoność problemu Dla ciągów jednakowej długości Backurs i Indyk wykazali w 2015 roku, że istnienie dokładnego algorytmu działającego w czasie dla dowolnej stałej przeczyłoby hipotezie SETH (Strong Exponential Time Hypothesis)Arturs Backurs, Piotr Indyk, „Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, s. 51–58, doi:10.1145/2746539.2746612.. Jest to zatem dolne ograniczenie warunkowe, a nie bezwarunkowy dowód konieczności czasu kwadratowego we wszystkich modelach obliczeń.
Warianty i odległości pokrewne W ważonej odległości edycyjnej poszczególne operacje mogą mieć różne koszty, a koszt zamiany może zależeć od pary symboli. Dowolnie dobrane koszty nie muszą zachowywać wszystkich własności metryki; na przykład koszty asymetryczne mogą naruszyć symetrię.
Odległość Damerau-Levenshteina rozszerza zestaw podstawowych operacji o zamianę miejscami dwóch sąsiednich symboli.
Odległość Hamminga stanowi przypadek ograniczony do zamian i do ciągów równej długości.