У статті наводиться розв'язок задачі пошуку відстані Левенштейна між рядками.
Досліджується її зв'язок із задачами знаходження найбільшої спільної підпослідовності
та оптимальним зіставленням рядків.
Розроблено метод визначення нижньої межі часової і об'ємної складності задачі. Доводиться неможливість існування поліноміального алгоритму розв'язання задачі мінімізації булевих функцій. Викладено алгоритм розв'язання задачі з фіксованою часовою складністю.