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

Độ phức tạp của bài toán đẳng cấu đồ thị

Còn mở

Cho hai đồ thị đơn hữu hạn $G_1 = (V_1, E_1)$ và $G_2 = (V_2, E_2)$ trên $n = |V_1| = |V_2|$ đỉnh, bài toán Đẳng cấu Đồ thị ( $\mathrm{GI}$ ) hỏi liệu có tồn tại một song ánh $\varphi : V_1 \to V_2$ sao cho $\{u, v\} \in E_1$ khi và chỉ khi $\{\varphi(u), \varphi(v)\} \in E_2$ hay không. Hỏi $\mathrm{GI}$ có thuộc lớp độ phức tạp $\mathsf{P}$ (thời gian đa thức tất định $n^{O(1)}$ ) hay không?

Người nêu, 1971Stephen Cook

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

Tính đến năm 2026, câu hỏi liệu Đẳng cấu Đồ thị có thuộc $\mathsf{P}$ hay không vẫn còn mở. Thuật toán thời gian tựa đa thức năm 2015–2017 của László Babai đã thiết lập chặn trên $\exp((\log n)^{O(1)})$ (và Harald Helfgott chỉ ra rằng số mũ trong $(\log n)^c$ có thể lấy bằng $c = 3$ ). Tiếp nối đột phá của Babai, thuật toán Weisfeiler–Leman số chiều đa logarit ( $(\log n)^{O(1)}$ - $\mathrm{WL}$ ) và các mở rộng quy hoạch động đã được phát triển, trong khi Jin-Yi Cai, Fürer và Immerman (1992) đã chứng minh không có phép thử $k$ - $\mathrm{WL}$ chiều cố định nào giải được $\mathrm{GI}$ trên mọi đồ thị.

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

Babai (2015–2017): Bài toán Đẳng cấu Đồ thị, Đẳng cấu Chuỗi và Giao Lớp ghép giải được trong thời gian tựa đa thức tất định $\exp((\log n)^{O(1)})$ .
Luks (1982) và Grohe–Neuen–Schweitzer (2018): với các đồ thị có bậc cực đại $d$ , tính đẳng cấu có thể kiểm tra được trong thời gian $n^{\operatorname{poly}(\log d)}$ .
Schöning (1988): $\mathrm{GI}$ nằm trong phân cấp thấp $\mathsf{Low}_2$ , và không thể là $\mathsf{NP}$ -đầy đủ trừ khi phân cấp đa thức sụp đổ về $\mathsf{\Sigma}_2^{\mathsf{P}} = \mathsf{\Pi}_2^{\mathsf{P}}$ .

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

Công cụ	Đạt được	Chỗ dừng
Phương pháp chia để trị nhóm hoán vị của Luks và chứng chỉ địa phương / Bổ đề Thiết kế của Babai	Rút gọn các tác động nhóm hoán vị khổng lồ $S_k$ hoặc $A_k$ trên đồ thị Johnson qua phép phân hoạch chính tắc $2$ bước với độ sâu đệ quy $O(\log n)$	Các hệ số phân nhánh nhân tính qua $O(\log n)$ tầng đệ quy tích lũy thành $n^{\operatorname{polylog}(n)}$ thay vì $n^{O(1)}$
Làm mịn màu Weisfeiler–Leman ( $k$ - $\mathrm{WL}$ )	Giải bài toán đẳng cấu trong thời gian đa thức trên hầu hết các đồ thị ngẫu nhiên và trên các đồ thị loại trừ một đồ thị con co rút cố định	Các đồ thị cấu kiện Cai–Fürer–Immerman (1992) buộc $k = \Omega(n)$ đối với thuật toán $k$ - $\mathrm{WL}$ thuần túy tổ hợp nếu không có quản lý lớp ghép lý thuyết nhóm

Câu hỏi còn mở

Bài toán Đẳng cấu Đồ thị có thuộc $\mathsf{P}$ hay không, tức là có thể giải được trong thời gian tất định $n^{O(1)}$ hay không?
Liệu số mũ $c$ trong thời gian chạy tựa đa thức $\exp(O((\log n)^c))$ của Đẳng cấu Đồ thị có thể giảm xuống dưới $3$ , hoặc về $1 + o(1)$ hay không?

Tài liệu tham khảo

László Babai (2016). Graph isomorphism in quasipolynomial time · DOI:10.1145/2897518.2897542 · arXiv:1512.03547
Eugene M. Luks (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time · DOI:10.1016/0022-0000(82)90009-5
Uwe Schöning (1988). Graph isomorphism is in the low hierarchy · DOI:10.1016/0022-0000(88)90010-4