Title: The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes Show Chinese title

Title: 切瓦塔尔-桑科夫问题：通过随机过程理解随机字符串比较

Abstract: Given two equally long, uniformly random binary strings, the expected length of their longest common subsequence (LCS) is asymptotically proportional to the strings' length. Finding the proportionality coefficient $\gamma$, i.e. the limit of the normalised LCS length for two random binary strings of length $n \to \infty$, is a very natural problem, first posed by Chv\'atal and Sankoff in 1975, and as yet unresolved. This problem has relevance to diverse fields ranging from combinatorics and algorithm analysis to coding theory and computational biology. Using methods of statistical mechanics, as well as some existing results on the combinatorial structure of LCS, we link constant $\gamma$ to the parameters of a certain stochastic particle process. These parameters are determined by a specific (large) system of polynomial equations with integer coefficients, which implies that $\gamma$ is an algebraic number. Short of finding an exact closed-form solution for such a polynomial system, which appears to be unlikely, our approach essentially resolves the Chv\'atal-Sankoff problem, albeit in a somewhat unexpected way with a rather negative flavour. Show Chinese abstract

Abstract: 给定两个长度相等的均匀随机二进制字符串，它们的最长公共子序列（LCS）的期望长度在渐近意义上与字符串的长度成正比。 找到比例系数$\gamma$，即两个长度为$n \to \infty$的随机二进制字符串的归一化 LCS 长度的极限，是一个非常自然的问题，最早由 Chvátal 和 Sankoff 在 1975 年提出，但至今仍未解决。 这个问题与从组合数学和算法分析到编码理论和计算生物学的多个领域都有关联。 利用统计力学的方法，以及一些关于 LCS 组合结构的现有结果，我们将常数$\gamma$与某种随机粒子过程的参数联系起来。 这些参数由一个特定的（大）多项式方程组决定，该方程组具有整数系数，这意味着$\gamma$是一个代数数。 在无法找到这种多项式系统的精确闭式解的情况下（这似乎不太可能），我们的方法基本上解决了 Chvátal-Sankoff 问题，尽管是以一种有些意外且带有相当负面色彩的方式。