Минимизация расстояния Левенштейна

[forspam86]

Дана строка $s$ в алфавите $\Sigma_1$ и строка $t$ в алфавите $\Sigma_2$, требуется найти инъективную функцию $f{:}\,\Sigma_1\rightarrow\Sigma_2$, минимизирующую расстояние Левенштейна (edit distance) между строками $f\!\left(s\right)$ и $t$ (функция $f$ задаёт гомоморфизм на строках). Размеры алфавитов не ограничены.
Что известно об алгоритмах (точных и приближённых) для этой задачи, о её сложности? Есть ли для неё хорошие известные эвристики?