The Chvátal–Sankoff problem: Understanding random string comparison through stochastic processes

Пусть даны две равномерно случайные двоичные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (longest common subsequence, LCS) асимптотически пропорционально длине строк. Естественным образом возникает проблема нахождения коэффициента этой пропорциональности $\gamma$, то есть предела нормализованной длины LCS двух случайных двоичных строк длины $n \to \infty$. Эта проблема была впервые сформулирована Хваталом (Chvátal) и Санкоффом (Sankoff) в 1975 г. и до сих пор не решена. Она имеет отношение к самым разнообразным областям исследований: от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. Применяя методы статистической механики, а также известные результаты о комбинаторной структуре LCS, мы устанавливаем связь между константой $\gamma$ и параметрами некоторого стохастического процесса взаимодействия частиц. Эти параметры определяются конкретной (большой по размеру) системой полиномиальных уравнений с целыми коэффициентами, из чего следует, что $\gamma$ является алгебраическим числом. Исключая потенциальную возможность найти решение такой системы в явном виде, которая представляется маловероятной, наш подход можно рассматривать как решение проблемы Хватала–Санкоффа, хотя и несколько неожиданное и отрицательное по духу. Библ. – 57 назв.