Bài toán mở, Tổ hợp và Toán rời rạc, Toán ứng dụng và Tính toán, nêu năm 1964

Giả thuyết Černý (ôtômat đồng bộ hóa)

Còn mở

Mọi ôtômat hữu hạn tất định (DFA) đồng bộ hóa có $n$ trạng thái đều có một từ đặt lại (từ đồng bộ hóa) $w \in \Sigma^*$ với độ dài tối đa $(n - 1)^2$ đưa tất cả $n$ trạng thái về cùng một trạng thái duy nhất: $|Q \cdot w| = 1$ .

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giả thuyết Černý vẫn còn mở, và ngay cả việc chứng minh một cận trên bậc hai $O(n^2)$ cho các ôtômat đồng bộ hóa tổng quát vẫn chưa giải được. Cận trên phổ quát tốt nhất hiện biết có dạng $\alpha n^3 + o(n^3)$ với $\alpha \le 0.1654$ (Shitov, 2019, tinh chỉnh kết quả của Szykuła, 2018), trong khi cận dưới lớn nhất đã biết vẫn là $(n - 1)^2$ , đạt được bởi họ $\mathcal{C}_n$ năm 1964 của Černý và chỉ hữu hạn các ôtômat cực trị đơn lẻ đã biết (đều có $n \le 6$ trạng thái). Giả thuyết đã được chứng minh cho các ôtômat Euler, phi tuần hoàn, vòng tròn, một cụm, đơn điệu định hướng, và đúng với xác suất cao cho các ôtômat đồng bộ hóa ngẫu nhiên.

Kết quả tốt nhất đã biết

Mọi DFA đồng bộ hóa $n$ trạng thái đều có từ đặt lại với độ dài không quá $\alpha n^3 + O(n^2)$ với $\alpha \approx 0.1654$ (Szykuła 2018; Shitov 2019), cải thiện cận cổ điển Pin–Frankl $\frac{n^3 - n}{6}$ .
Cận Černý $(n - 1)^2$ đã được chứng minh cho ôtômat Euler (Kari, 1998), ôtômat vòng tròn (Dubuc, 1998), ôtômat phi tuần hoàn (Trahtman, 2007) và ôtômat một cụm có chu trình độ dài nguyên tố (Steinberg, 2011).

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Định lý tập hợp giao chéo lệch của Frankl và kỹ thuật từ né tránh	Chặn độ dài từ ngắn nhất nén một tập con trạng thái $S$ cỡ $k \ge 2$ xuống cỡ $k - 1$ bởi $\binom{n - k + 2}{2}$ (Pin–Frankl) và tinh chỉnh cận này thông qua các cận hạng đại số tuyến tính trên từ né tránh (Szykuła, Shitov).	Việc cộng dồn $O((n - k)^2)$ bước nén theo $k = n, n-1, \dots, 2$ tất yếu sinh ra cận $O(n^3)$ , trừ khi chứng minh được chi phí nén khấu hao chỉ là $O(n)$ cho mỗi bước.
Biểu diễn đại số tuyến tính của vị nhóm chuyển trạng thái (Kari, Steinberg)	Gắn ma trận cho các chữ cái đầu vào và dùng lập luận số chiều trong $\mathbb{R}^n$ kết hợp với phân bố dừng của đồ thị có hướng nền để thiết lập cận $O(n^2)$ cho các ôtômat Euler và ôtômat một cụm.	Các ôtômat đồng bộ hóa tổng quát không có vectơ dừng dương hay tính chất bậc vào đồng đều, nên trọng số nghịch ảnh không nhất thiết tăng đơn điệu dọc theo các từ ngắn.

Câu hỏi còn mở

Có tồn tại một hằng số phổ quát $C > 0$ sao cho mọi DFA đồng bộ hóa $n$ trạng thái đều có một từ đặt lại với độ dài bậc hai tối đa $C n^2$ hay không?
Với $n \ge 7$ , liệu ôtômat $\mathcal{C}_n$ của Černý có phải là ôtômat đồng bộ hóa $n$ trạng thái tối tiểu duy nhất (sai khác phép đẳng cấu và các chữ cái dư thừa) đạt tới ngưỡng đặt lại $(n - 1)^2$ hay không?

Tài liệu tham khảo

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