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
Trong định nghĩa trên, nên xem formula_13 là một ma trận formula_14 (gọi là "ma trận dữ liệu vào") trong đó mỗi hàng ứng với một giá trị formula_6 formula_7 X và mỗi cột ứng với một formula_8 formula_7 Y. Mỗi phần tử của ma trận dữ liệu vào formula_19. Ban đầu cả Alice và Bob đều có một bản sao của toàn bộ ma trận A (giả sử cả hai người đều biết hàm formula_13). Khi đó, bài toán tính giá trị hàm số có thể xem là việc định vị giá trị cần tính trên ma trận. Bài toán này có thể giải được nếu Alice hoặc Bob biết cả formula_6 và formula_8. Khi mới bắt đầu, bất kì một trong số formula_23 phần tử của ma trận đều có thể là giá trị cần tính. Sau đó sau mỗi lần một người gửi đi 1 bit cho người kia, một số hàng/cột bị loại đi và thu được một ma trận con của A.
Một tập hợp R formula_24 X formula_2 Y được gọi là một "hình chữ nhật (tổ hợp)" nếu bất kì khi nào formula_26 formula_7 R và formula_28 formula_7 R thì formula_30 formula_7 R. Một cách tương đương, R là một ma trận con của A sao cho R = M formula_2 N trong đó M formula_24 X và N formula_24 Y. Xét thời điểm hai người đã trao đổi formula_35 bit. Với một giá trị cố định formula_36 formula_7 formula_38, định nghĩa
Khi đó, formula_41 formula_24 X formula_2 Y, và formula_41 là một hình chữ nhật của A.