Дана строка

в алфавите

и строка

в алфавите

, требуется найти инъективную функцию

, минимизирующую расстояние Левенштейна (edit distance) между строками

и

(функция

задаёт гомоморфизм на строках). Размеры алфавитов не ограничены.
Что известно об алгоритмах (точных и приближённых) для этой задачи, о её сложности? Есть ли для неё хорошие известные эвристики?