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

Giả thuyết trò chơi duy nhất (Unique Games)

Còn mở

Với mọi $\varepsilon > 0$ , tồn tại kích thước bảng chữ cái $k = k(\varepsilon)$ sao cho khi cho một thực thể phủ nhãn duy nhất trên bảng chữ cái cỡ $k$ (trong đó mỗi ràng buộc giữa hai biến $u, v$ là một song ánh $\pi_{u,v} : [k] \to [k]$ ), bài toán phân biệt giữa trường hợp tồn tại cách gán nhãn thỏa mãn ít nhất tỷ lệ $1 - \varepsilon$ số ràng buộc và trường hợp không có cách gán nhãn nào thỏa mãn quá tỷ lệ $\varepsilon$ số ràng buộc là NP-khó.

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

Tính đến năm 2026, toàn bộ giả thuyết trò chơi duy nhất với ràng buộc $1$ -đối- $1$ vẫn còn mở. Đột phá năm 2018 giải quyết giả thuyết trò chơi $2$ -đối- $2$ của Khot, Minzer và Safra đã chứng minh tính NP-khó của việc phân biệt các trò chơi duy nhất thỏa mãn được tỷ lệ $(1/2 - \varepsilon)$ với tỷ lệ $\varepsilon$ , mang lại cận độ khó xấp xỉ vô điều kiện gần $\sqrt{2}$ cho bài toán phủ đỉnh, trong khi việc thu hẹp khoảng cách từ độ đầy đủ $1/2$ lên $1 - \varepsilon$ vẫn là thách thức trung tâm.

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

Định lý trò chơi $2$ -đối- $2$ (Khot–Minzer–Safra 2018) chứng minh rằng với mọi $\varepsilon > 0$ , việc phân biệt các thực thể Unique Games có giá trị ít nhất $1/2 - \varepsilon$ với các thực thể có giá trị tối đa $\varepsilon$ là NP-khó.
Các thuật toán thời gian dưới hàm mũ (Arora–Barak–Steurer 2010) giải được Unique Games với độ đầy đủ $1 - \varepsilon$ trong thời gian $\exp(k \cdot n^{\varepsilon^{O(1)}})$ nhờ phân hoạch đồ thị phổ và phân cấp Lasserre/Tổng bình phương.

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

Công cụ	Đạt được	Chỗ dừng
Giải tích Fourier rời rạc trên siêu lập phương Boole và định lý Đa số ổn định nhất	Chuyển giả thuyết trò chơi duy nhất thành các cận không thể xấp xỉ chặt cho Max-Cut, Max-2SAT và các bài toán thỏa mãn ràng buộc tổng quát thông qua kiểm định độc tài	Chỉ chứng minh độ khó có điều kiện khi giả sử UGC đúng, chứ không tự chứng minh tính NP-khó của bản thân Unique Games
Tính giãn nở của đồ thị Grassmann và giải tích Fourier phi giao hoán	Đặc trưng hóa các tập không giãn nở trong đồ thị Grassmann qua cấu trúc phóng to – thu nhỏ, chứng minh được giả thuyết trò chơi $2$ -đối- $2$	Mất đi hệ số $2$ ở độ đầy đủ một cách bản chất khi quy dẫn từ ràng buộc $2$ -đối- $2$ sang ràng buộc song ánh $1$ -đối- $1$ , nên dừng lại ở độ đầy đủ $1/2 - \varepsilon$

Câu hỏi còn mở

Liệu giả thuyết trò chơi duy nhất có đúng với độ đầy đủ $1 - \varepsilon$ cho mọi $\varepsilon > 0$ , hay tồn tại thuật toán thời gian đa thức phân biệt các thực thể thỏa mãn được tỷ lệ $(1 - \varepsilon)$ với các thực thể thỏa mãn được tỷ lệ $\varepsilon$ ?

Tài liệu tham khảo

Subhash Khot (2002). On the power of unique 2-prover 1-round games · DOI:10.1145/509907.510017
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? · DOI:10.1137/S0097539705447372
Prasad Raghavendra (2008). Optimal algorithms and inapproximability results for every CSP? · DOI:10.1145/1374376.1374414
Subhash Khot, Dor Minzer, Muli Safra (2023). Pseudorandom sets in Grassmann graph have near-perfect expansion · DOI:10.4007/annals.2023.198.1.1