Điện toán & AI · thí nghiệm
Vượt qua giới hạn
Một mạng lưới, một nhóm người đều quen biết lẫn nhau, một lối tắt từ năm 1985 qua phép nhân ma trận, và một giả thuyết đứng vững suốt nhiều thập kỷ. Bốn câu hỏi, từ cơ bản đến nâng cao, về hồi kết của Giả thuyết k-Clique.
1 · Nêu điều đã được chứng minh
Cơ bản
Bài viết cho thấy điều gì về Giả thuyết k-Clique?
2 · Tính chi phí của năm 1985
Phương pháp Nešetřil–Poljak tìm một k-clique trong khoảng n^(ωk/3) bước. Hãy lấy k = 9 và ω = 2, giá trị thấp nhất mà ω có thể có.
Trung cấp
Phương pháp năm 1985 cho số mũ nào của n?
3 · Giải thích chữ “ngay cả khi ω = 2”
Giả thuyết dự đoán một chi phí n^(ωk/3). Giá trị chính xác của ω chưa được biết: nó ít nhất bằng 2, và bài viết trích dẫn một cận trên là 9/4.
Nâng cao
Vì sao việc mức tiết kiệm mới đúng với mọi giá trị của ω, kể cả ω = 2, lại quan trọng?
4 · Chuyển mức lợi sang bài toán khác
Max-2-CSP, bao gồm Max-Cut và Max-2-SAT, với n biến Boole, từng được giải trong khoảng 2^(ωn/3) bước. Hãy chia các biến thành chín nhóm, và mỗi phép gán của một nhóm trở thành một đỉnh của một bài toán 9-clique có trọng số.
Nâng cao
Thuật toán clique mới mang lại gì cho các bài toán này?
Đã vượt qua giới hạn
—