"Записки научных семинаров ПОМИ"

Том 517, стр. 191-224

Проблема Хватала--Санкоффа: Осмысление сравнения случайных строк через стохастические процессы

А. Тискин

Department of Mathematics and Computer Science, St.Petersburg State University, 7/9 Universitetskaya nab., St.Petersburg, 199034 Russia

alextiskin@gmail.com

Аннотация: Пусть даны две равномерно случайные двоичные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (longest common subsequence, LCS) асимптотически пропорционально длине строк. Естественным образом возникает проблема нахождения коэффициента этой пропорциональности $\gamma$, то есть предела нормализованной длины LCS двух случайных двоичных строк длины $n \to \infty$. Эта проблема была впервые сформулирована Хваталом (Chv\'atal) и Санкоффом (Sankoff) в 1975 г. и до сих пор не решена. Она имеет отношение к самым разнообразным областям исследований: от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. Применяя методы статистической механики, а также известные результаты о комбинаторной структуре LCS, мы устанавливаем связь между константой $\gamma$ и параметрами некоторого стохастического процесса взаимодействия частиц. Эти параметры определяются конкретной (большой по размеру) системой полиномиальных уравнений с целыми коэффициентами, из чего следует, что $\gamma$ является алгебраическим числом. Исключая потенциальную возможность найти решение такой системы в явном виде, которая представляется маловероятной, наш подход можно рассматривать как решение проблемы Хватала--Санкоффа, хотя и несколько неожиданное и отрицательное по духу. Библ. -- 57 назв.
Ключевые слова: случайные строки, наибольшая общая подпоследовательность, %проблема Хватала--Санкоффа, процессы взаимодействия частиц [random strings, longest common subsequence, the Chv\'atal--Sankoff problem, particle processes]

Полный текст(.pdf)