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
Độ phức tạp ngẫu nhiên được định nghĩa là số bit cần trao đổi trong trường hợp xấu nhất của giao thức.
Cũng có thể định nghĩa giao thức ngẫu nhiên với lỗi một mặt một cách tương tự.
Giao thức ngẫu nhiên cho ví dụ EQ.
Quay lại với ví dụ "EQ", nếu được phép có lỗi, thì Alice và Bob có thể kiểm tra đẳng thức bằng cách trao đổi "O(log n)" bit. Xét giao thức sau: giả sử Alice và Bob đều biết một xâu ngẫu nhiên công cộng formula_71. Alice tính formula_72 và gửi "b" cho Bob. Ký hiệu formula_73 là phép tính tích vô hướng trong GF(2). Sau đó Bob so sánh "b" với formula_74. Nếu chúng bằng nhau, thì Bob chấp nhận, đưa ra kết quả "x" bằng "y". Nếu không, Bob từ chối.
Rõ ràng, nếu formula_75, thì formula_76, nên formula_77chấp nhậnformula_78. Nếu "x" không bằng "y", vẫn có khả năng formula_76, dẫn đến việc Bob đưa ra câu trả lời sai.
Nếu "x" và "y" khác nhau, tồn tại ít nhất một vị trí chúng khác nhau. Không mất tính tổng quát, giả sử tại vị trí thứ "i", formula_80 và formula_81. Với mọi xâu ngẫu nhiên "z" sao cho formula_82, xét xâu "z' " giống hệt như "z" ngoại trừ vị trí thứ "i". Khi đó, formula_83. Vì vậy formula_77chấp nhậnformula_85. Giao thức này có thể được lặp lại nhiều lần để giảm xác suất sai.
Như vậy "nếu Alice và Bob có chung một xâu ngẫu nhiên công cộng n bit", họ có thể tính được formula_86 chỉ bằng việc gửi đi 1 bit. Trong phần dưới đây, ta sẽ xét một phương pháp giả lập một giao thức dùng "O(n)" bit ngẫu nhiên công cộng bằng một giao thức với xâu ngẫu nhiên riêng với số bit cần trao đổi tăng thêm "O(log n)" bit. Như vậy, tồn tại giao thức sử dụng xâu ngẫu nhiên riêng cho "EQ" chỉ trao đổi "O(log n)" bit.