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
Dãy các bit được gửi đi giữa Alice và Bob được gọi là "lịch sử" thực hiện của giao thức. Có thể xem quá trình thực hiện giao thức là như sau. Ban đầu tập hợp giá trị có thể là toàn bộ ma trận A. Ở mỗi bước, sau khi một bit được gửi đi, hai người thu hẹp được tập hợp các giá trị có thể thành một hình chữ nhật con của tập hợp giá trị ở bước trước. Cuối cùng khi toàn tất giao thức, tùy thuộc vào hình chữ nhật ở bước cuối cùng mà Alice và Bob quyết định giá trị hàm số là bao nhiêu. Nếu giao thức luôn tính đúng thì tất cả các phần tử của hình chữ nhật sau bước cuối cùng phải bằng nhau và Alice và Bob quyết định được giá trị cần tính chính là giá trị đó.
Ví dụ hàm đẳng thức.
Trong phần này, ta xét ví dụ trong đó Alice và Bob muốn xác định xem dữ liệu vào của họ có bằng nhau hay không. Nghĩa là ta muốn xác định xem formula_6 có bằng formula_8. Có thể chứng minh bài toán tính hàm đẳng thức (ký hiệu là EQ) luôn đòi hỏi trao đổi formula_47 bit trong trường hợp xấu nhất.
Trước hết, xét ví dụ formula_6 và formula_8 có 3 bit. Hàm đẳng thức được mô tả bởi ma trận dưới đây.Các hàng ứng với các giá trị của formula_6, và các cột ứng với các giá trị của formula_8.
Theo ma trận trên, hàm chỉ nhận giá trị 1 khi formula_6 bằng formula_8 (các phần tử trên đường chéo chính). Có thể nhận thấy việc gửi đi 1 bit dữ liệu vào giảm số khả năng đi 2 lần. Chẳng hạn, nếu ta biết bit đầu tiên của formula_8 là 1, thì chỉ cần xem xét một nửa số cột (trong đó formula_8 bằng 100, 101, 110, hoặc 111).
Định lý: formula_56.&lt;br&gt;
Chứng minh. Giả sử cho mục đích phản chứng formula_57. Nghĩa là tồn tại hai bộ dữ liệu vào khác nhau formula_58 và formula_59 có cùng một lịch sử formula_36. Vì mỗi lịch sử luôn xác định một hình chữ nhật, và formula_61 nên formula_62. Theo giả thuyết formula_63 nên giá trị đúng của hàm đẳng thức phải là 0 (mâu thuẫn).