Bài toán mở, Tô pô, Toán ứng dụng và Tính toán, nêu năm 1910

Bài toán tháo nút (độ phức tạp nhận diện nút tầm thường)

Giải một phần

Cho một sơ đồ nút $D$ trên mặt phẳng có $n$ giao điểm biểu diễn một nút $K \subset S^3$ , hãy quyết định bằng thuật toán — và xác định liệu có thể quyết định trong thời gian đa thức $O(n^c)$ hay không — xem $K$ có đồng luân môi trường với nút tầm thường $S^1 \subset S^3$ hay không.

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

Tính đến năm 2026, bài toán tháo nút đã được chứng minh vô điều kiện là nằm trong $\mathsf{NP} \cap \mathsf{coNP}$ , và công bố năm 2021 của Marc Lackenby đưa ra thuật toán thời gian tựa đa thức chạy trong $n^{O(\log n)}$ bước, đặt bài toán nhận diện nút tầm thường ngang hàng với bài toán đẳng cấu đồ thị như một trong những bài toán tự nhiên tiêu biểu nhất thuộc $\mathsf{NP} \cap \mathsf{coNP}$ có độ phức tạp tựa đa thức nhưng vẫn chưa rõ có thuộc lớp $\mathsf{P}$ hay không. Trên thực tế, các thuật toán dựa trên quy hoạch tuyến tính trên mặt chuẩn tắc (phần mềm Regina) và rút gọn phân lá bện chạy rất nhanh trên các sơ đồ hàng trăm giao điểm, nhưng việc chứng minh thời gian đa thức trường hợp xấu nhất $O(n^c)$ vẫn là bài toán mở.

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

Nhận diện nút tầm thường nằm vô điều kiện trong $\mathsf{NP} \cap \mathsf{coNP}$ (Hass–Lagarias–Pippenger 1999 cho $\mathsf{NP}$ ; Kuperberg 2014 có điều kiện trên GRH và Lackenby 2016/2021 vô điều kiện cho $\mathsf{coNP}$ ).
Mọi sơ đồ $n$ giao điểm của nút tầm thường đều có thể tháo gỡ sau tối đa $(236\,n)^{11}$ phép biến đổi Reidemeister (Lackenby, 2015).
Thuật toán tất định nhanh nhất đã biết chạy trong thời gian tựa đa thức $n^{O(\log n)}$ (được Lackenby công bố năm 2021).

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

Công cụ	Đạt được	Chỗ dừng
Mặt chuẩn tắc và phân cấp đa tạp khâu (Haken, Hass–Lagarias–Pippenger, Lackenby)	Đặt bài toán nhận diện nút tầm thường hoàn toàn vô điều kiện vào $\mathsf{NP} \cap \mathsf{coNP}$ và mang lại thuật toán tựa đa thức $n^{O(\log n)}$ thông qua việc duyệt hiệu quả các phân cấp đa tạp khâu	Việc phân nhánh qua $O(\log n)$ tầng của một phân cấp đa tạp khâu làm nhân bội các lựa chọn đa thức ở mỗi độ sâu, dẫn đến thời gian $n^{O(\log n)}$ thay vì $n^{O(1)}$
Biểu diễn nhóm vào $\operatorname{SL}(2,\mathbb{C})$ và $\operatorname{SL}(2,\mathbb{F}_p)$ (Kronheimer–Mrowka, Kuperberg)	Chứng nhận tính thắt nút bằng cách chỉ ra một đồng cấu không giao hoán $\pi_1(S^3 \setminus K) \to \operatorname{SL}(2,\mathbb{F}_p)$ với số nguyên tố $p$ có độ dài bit đa thức (dưới giả thuyết GRH)	Cho một chứng chỉ không tất định ngắn gọn về tính thắt nút, nhưng việc tìm biểu diễn đó một cách tất định đòi hỏi giải hệ phương trình đa thức bằng cơ sở Gröbner, tốn thời gian hàm mũ trong trường hợp xấu nhất

Câu hỏi còn mở

Bài toán tháo nút có thể giải được trong thời gian đa thức tất định $\mathsf{P}$ hay không?
Có tồn tại chặn trên tuyến tính hoặc bậc hai $O(n^2)$ cho số phép biến đổi Reidemeister cần thiết để tháo gỡ mọi sơ đồ $n$ giao điểm của nút tầm thường hay không?

Tài liệu tham khảo

Wolfgang Haken (1961). Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten · DOI:10.1007/BF02559591
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger (1999). The computational complexity of knot and link problems · DOI:10.1145/301970.301971 · arXiv:math/9807016v1
Marc Lackenby (2015). A polynomial upper bound on Reidemeister moves · DOI:10.4007/annals.2015.182.2.3 · arXiv:1302.0180v3
Marc Lackenby (2021). The efficient certification of knottedness and Thurston norm · DOI:10.1016/j.aim.2021.107796 · arXiv:1604.00290v1