1244095
Độ phức tạp truyền thông
https://vi.wikipedia.org/wiki?curid=1244095
Title: Độ phức tạp truyền thông
Khái niệm độ phức tạp truyền thông được đưa ra bởi Andrew Yao năm 1979,
khi nghiên cứu về việc hai người độc lập nhau (Alice và Bob) cùng cộng tác để thực hiện một công việc tính toán. Alice nhận được một xâu "n"-bit, ký hiệu là "x", và Bob nhận được một xâu "n"-bit khác, ký hiệu là "y". Mục tiêu là cuối cùng một trong hai người (ví dụ Bob) tính được giá trị một hàm sau khi hai người trao đổi một lượng thông tin ít nhất có thể. Ghi chú là ta không quan tâm đến số phép tính hay lượng bộ nhớ cần dùng. Độ phức tạp truyền thông là ngành nghiên cứu lượng thông tin cần truyền trong những bài toán tính toán phân tán như vậy.
Dĩ nhiên họ luôn đạt được mục tiêu bằng cách để Alice gửi toàn bộ xâu "n"-bit cô nhận được cho Bob, và sau đó Bob tính giá trị hàm số f, nhưng trong nhiều trường hợp, tùy vào hàm f, có thể giải quyết được bài toán với lượng bit cần trao đổi ít hơn n rất nhiều.
Bài toán trừu tượng này có nhiều ứng dụng: chẳng hạn trong thiết kế mạch VLSI, ta muốn cực tiểu hóa năng lượng cần dùng bằng cách giảm lượng tín hiệu điện cần gửi đi giữa các thành phần khác nhau trong quá trình tính toán. Bài toán này cũng có ứng dụng trong nghiên cứu cấu trúc dữ liệu, và tối ưu hóa mạng máy tính.
Định nghĩa.
Xét hàm số formula_1: X formula_2 Y formula_3 Z trong đó ta giả sử formula_4 và formula_5. Alice nhận được dữ liệu vào là một xâu n-bit formula_6 formula_7 X và Bob nhận được một xâu n-bit formula_8 formula_7 Y. Bằng cách gửi đi cho nhau mỗi lần 1 bit (theo một "giao thức truyền thông" nhất định), Alice và Bob muốn tính giá trị hàm formula_10 sao cho khi thực hiện xong, ít nhất một trong hai người biết giá trị của hàm. Dễ thấy sau khi một trong hai người biết kết quả thì chỉ cần người đó gửi kết quả cho người kia (bằng 1 bit) thì cả hai người đều biết kết quả. Độ phức tạp truyền thông xấu nhất của hàm , ký hiệu là formula_11, được định nghĩa là