未解决问题，组合数学与离散数学, 应用与计算数学，1964年提出

切尔尼猜想（同步自动机）

未解决

任意具有 $n$ 个状态的同步确定性有限自动机（DFA）都存在一个长度不超过 $(n - 1)^2$ 的复位词（同步词） $w \in \Sigma^*$ ，能将全部 $n$ 个状态映射到同一个状态，即满足 $|Q \cdot w| = 1$ 。

研究前沿截至2026年

截至2026年，切尔尼猜想依然悬而未决，甚至对一般同步自动机证明二次上界 $O(n^2)$ 也尚未实现。目前已知最优普适上界为 $\alpha n^3 + o(n^3)$ ，其中 $\alpha \le 0.1654$ （希托夫于2019年改进什库瓦2018年结果所得）；而已知最坏下界仍为 $(n - 1)^2$ ，仅由切尔尼1964年构造的自动机族 $\mathcal{C}_n$ 及有限多个已知零散极值自动机（均满足 $n \le 6$ ）达到。该猜想已对欧拉、非周期、循环、单簇和有向单调自动机获证，并对随机同步自动机以高概率成立。

已知最佳结果

任意 $n$ 状态同步DFA都存在长度不超过 $\alpha n^3 + O(n^2)$ （其中 $\alpha \approx 0.1654$ ）的复位词（什库瓦 2018；希托夫 2019），改进了经典的潘–弗兰克尔界 $\frac{n^3 - n}{6}$ 。
切尔尼界 $(n - 1)^2$ 已对欧拉自动机（卡里，1998）、循环自动机（迪比克，1998）、非周期自动机（特拉赫特曼，2007）以及具有素数长圈的单簇自动机（斯坦伯格，2011）获证。

使用的方法及其局限

方法	取得的结果	局限所在
弗兰克尔斜交叉集定理与回避词技术	将把规模为 $k \ge 2$ 的状态子集 $S$ 压缩至规模 $k - 1$ 的最短词长界定为 $\binom{n - k + 2}{2}$ （潘–弗兰克尔），并借助回避词上的线性代数秩估计加以改进（什库瓦、希托夫）。	对 $k = n, n-1, \dots, 2$ 逐一累加每步 $O((n - k)^2)$ 的压缩代价必然导致 $O(n^3)$ 量级的上界，除非能够证明每步压缩具有 $O(n)$ 的均摊上界。
转移幺半群的线性代数表示（卡里、斯坦伯格）	将输入字母表示为矩阵，并结合底层有向图的平稳分布与 $\mathbb{R}^n$ 中的维数论证，为欧拉自动机和单簇自动机建立了 $O(n^2)$ 上界。	一般同步自动机缺乏正平稳向量或均匀入度性质，因此原像权重未必能沿着短词单调增长。

尚未解决的问题

是否存在普适常数 $C > 0$ ，使得任意 $n$ 状态同步DFA都存在长度不超过 $C n^2$ 的二次量级复位词？
当 $n \ge 7$ 时，达到复位阈值 $(n - 1)^2$ 的极小 $n$ 状态同步自动机（在同构与冗余字母意义下）是否唯有切尔尼自动机 $\mathcal{C}_n$ ？

参考文献

Mikhail V. Volkov (2008). Synchronizing automata and the Černý conjecture · DOI:10.1007/978-3-540-78926-0_2
Marek Szykuła (2018). Improving the upper bound on the length of the shortest reset word · DOI:10.4230/LIPIcs.STACS.2018.56 · arXiv:1702.05455
Yaroslav Shitov (2019). An improvement to a recent upper bound for synchronizing words of finite automata · DOI:10.1016/j.jcta.2019.04.007 · arXiv:1901.06542