Großer Durchbruch beim fairen Aufteilen
Đột phá lớn trong chia đôi công bằng
This reading was translated and simplified for German learners. The original content belongs to Quanta.
Select a word or phrase to look it up, translate it, highlight it, or add a note.
Reading progress
Paragraph 1/25
Read the German first. Reveal the translation below any paragraph when needed.
Vietnamese translation
Sau 30 năm, các nhà khoa học máy tính cuối cùng cũng tìm ra cách tốt hơn để chia các đối tượng thành hai nhóm một cách công bằng.
Vietnamese translation

Vietnamese translation
Chia 12 người thành hai đội cho một cuộc thi kiến thức không cần bằng tiến sĩ toán học. Tuy nhiên, mỗi người có điểm mạnh và yếu khác nhau. Người này giỏi địa lý nhưng không biết gì về âm nhạc. Người kia rành thiên nhiên nhưng không xem truyền hình. Một người nữa yêu điện ảnh nhưng không bao giờ đọc sách. Việc phân phối đều các thế mạnh này cho hai đội trở nên khó khăn hơn nhiều.
Vietnamese translation
Vậy làm sao để tạo ra những đội cân bằng nhất? Làm thế nào để cả hai đội có sức mạnh ngang nhau trong mọi lĩnh vực, từ thần thoại Hy Lạp đến bóng rổ đại học?
Vietnamese translation
Các nhà nghiên cứu chuyên về lý thuyết sai lệch tổ hợp khẳng định: Luôn có cách để tạo ra hai đội cân bằng đến mức bất ngờ.
Vietnamese translation
Lý thuyết sai lệch là một phần của toán học. Nó liên quan đến việc phân bổ tài nguyên sao cho công bằng nhất có thể. Nếu một đội thi có tất cả kiến thức lịch sử trong khi đội kia không biết gì, đó chính là một sự sai lệch lớn.
Vietnamese translation
Vào đầu thập niên 1980, nhà toán học János Komlós đưa ra một giả thuyết gây ngạc nhiên. Ông nói: Dù có bao nhiêu đối tượng (ví dụ như thí sinh) hay bao nhiêu chiều (ví dụ như các chủ đề thi), sai lệch sẽ không bao giờ vượt quá một con số cố định. Sai lệch có thể được đo đạc. Và luôn tồn tại một cách để chia đội sao cho sai lệch nằm dưới con số cố định đó.
Vietnamese translation
"Điều đó thực sự đáng kinh ngạc," Haotian Jiang nhận xét. Ông là nhà lý thuyết máy tính tại Đại học Chicago. "Giả thuyết Komlós nói rằng: Chiều của vấn đề không quan trọng. Đó là một hằng số phổ quát."
Vietnamese translation
Cho đến nay, chưa ai tìm ra bằng chứng nào chứng minh giả thuyết này sai. Nhưng nó quá đáng kinh ngạc đến mức một số nhà toán học tin rằng nó phải sai. Nikhil Bansal, nhà lý thuyết máy tính tại Đại học Michigan, gọi đây là "một trong những vấn đề thánh bách trong lý thuyết sai lệch".
Vietnamese translation
Ngay cả người đặt ra giả thuyết cũng thấy nó hơi vô lý. Komlós, hiện đã nghỉ hưu, đùa trong một email: "Tôi còn trẻ và ngu ngốc khi đưa ra giả thuyết đó. Tôi đã mang lại vấn đề cho lý thuyết sai lệch tổ hợp với giả thuyết vô trách nhiệm này."
Vietnamese translation
Nếu giả thuyết Komlós đúng, nó có thể giải đáp nhiều vấn đề khác. Điều này áp dụng cho cả lý thuyết sai lệch nói riêng và các lĩnh vực khác như nghiên cứu vận hành nói chung.
Vietnamese translation
Tuy nhiên, trong nhiều thập kỷ, một lời giải dường như rất khó đạt được. Các nhà toán học không tiến triển được nhiều. Giới hạn trên tốt nhất của họ về sai lệch có từ năm 1998. Giới hạn này vẫn phụ thuộc nhiều vào chiều của vấn đề. Nó cách xa một hằng số.
Vietnamese translation
Rồi, vào mùa thu năm 2025, Bansal và Jiang công bố bước đột phá lớn đầu tiên sau gần 30 năm. Họ tìm ra một giới hạn chỉ thay đổi rất chậm theo chiều vấn đề. Ngay cả với một số lượng chiều khổng lồ, nó chỉ hơi lệch so với một hằng số. Các nhà nghiên cứu khác mô tả công trình này, sử dụng một phương pháp thuật toán mới, là "rất thúirected", "một kết quả đẹp" và "một bước tiến khổng lồ".
Vietnamese translation
Kết quả bất ngờ này chưa giải quyết hoàn toàn vấn đề. Nhưng nó là bằng chứng mạnh mẽ nhất cho đến nay cho thấy giả thuyết của Komlós không hề vô trách nhiệm. Aleksandar Nikolov, nhà khoa học máy tính tại Đại học Toronto, nói: "Trước đây tôi nghi ngờ giả thuyết sai. Công trình mới này khiến tôi tin rằng giả thuyết có lẽ đúng."
Vietnamese translation
Giải pháp của Bansal và Jiang cho thấy: Các hệ thống phức tạp có thể được đơn giản hóa và dễ nghiên cứu hơn nhiều. Nó cũng mang lại những ý tưởng có thể áp dụng trong toán học, vật lý và thậm chí là học máy.
Vietnamese translation
Chia thành hai nhóm
Vietnamese translation
Các vấn đề sai lệch kiểu Komlós liên quan đến việc chia một tập hợp các đối tượng thành hai tập con. Bạn có thể hình dung việc chia người thành hai đội thi, hoặc chia ô tô cũ thành hai nhóm, hoặc chia người tham gia nghiên cứu y khoa thành nhóm điều trị và nhóm giả dược.
Vietnamese translation
Giả thuyết Komlós hình dung mỗi người (hoặc đối tượng) là một mũi tên có độ dài 1. Đó được gọi là đơn vị vector. Vector này có một danh sách tọa độ. Mỗi tọa độ chỉ ra mức độ một đặc điểm cụ thể mà người đó có.
Vietnamese translation
Hãy tưởng tượng chỉ xem hai lĩnh vực thi: Sách và Phim. Mỗi người có thể được hình dung như một vector:
Vietnamese translation
Vietnamese translation
Bây giờ, gán mỗi vector cho một đội. Nếu đặt một vector vào Đội A, giữ nguyên các tọa độ của nó. Nếu đặt vào Đội B, nhân mỗi tọa độ với −1. Tức là bạn "đảo ngược" vector đó.
Vietnamese translation
Nếu có thể chia hoàn hảo và cả hai đội có kiến thức ngang nhau về sách và phim, tổng tất cả các vector sẽ bằng không. Đó là sự cân bằng hoàn hảo.
Vietnamese translation
Nhưng sự hoàn hảo thường là không thể. Vì vậy câu hỏi là: Làm sao để tổng tiến gần không nhất có thể?
Vietnamese translation
Trong ví dụ với bốn thí sinh, bạn có thể thử tất cả các khả năng một cách dễ dàng. Rồi bạn thấy: Alice và Bob nên ở một đội, Carla và Dave ở đội kia. Lưu ý không cần chia số lượng người bằng nhau. Bạn chỉ cần chia các vector sao cho càng nhiều vector được nhân với −1 càng tốt để chúng triệt tiêu nhau.
Vietnamese translation
Nhiệm vụ này trở nên khó khăn hơn nhiều khi có nhiều vector hơn và nhiều đặc điểm cần cân bằng. Tuy nhiên, Komlós đã đưa ra một giả thuyết rất lạc quan: Dù có bao nhiêu vector và chiều, sai lệch luôn nằm dưới một hằng số cố định.
