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

Пусть заданы две равномерно случайные бинарные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (LCS) асимптотически пропорционально длине строк. Нахождение коэффициента $\gamma$ этой пропорциональности, то есть предела нормализованной длины LCS для пары случайных бинарных строк длины $n \to \infty$ - естественная проблема, впервые сформулированная Хваталом и Санковым в 1975 году и до сих пор не решенная. Данная проблема возникает в различных областях исследований, от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. Используя методы статистической механики, а также предыдущие результаты о комбинаторной структуре LCS в сочетании с элементарной теорией вероятностей, мы связываем константу $\gamma$ с параметрами определенного стохастического процесса взаимодействия частиц. Эти параметры, в свою очередь, выражаются определенной (весьма большой) системой полиномиальных уравнений с целыми коэффициентами, в силу чего $\gamma$ является алгебраическим числом. Ввиду сложности данной системы, единственным практическим способом ее решения представляется компьютерная симуляция стохастического процесса, при помощи которого она получена, что дает новую численную оценку для значения $\gamma$. Исключая маловероятный случай существования явного решения для данной системы, предлагаемый подход является по сути решением проблемы Хватала-Санкова, хотя и несколько неожиданным по форме и отрицательным по духу.