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
Ngẫu nhiên công cộng và riêng.
Rõ ràng các bit ngẫu nhiên công cộng làm cho việc trao đổi thông tin dễ dàng hơn. Tuy nhiên, vẫn có thể sử dụng các giao thức dùng bit ngẫu nhiên công cộng ngay cả khi không có các bit này mà chỉ cần trao đổi thêm một số nhỏ bit. Mọi giao thức sử dụng formula_47-bit ngẫu nhiên công cộng đều có thể giả lập bằng việc trao đổi "O(log n)" bit.
Một cách trực giác, ta tìm một tập hợp nhỏ các xâu có đủ độ ngẫu nhiên sao cho khi thực hiện giao thức ngẫu nhiên trên tập nhỏ này, xác suất sai chỉ tăng thêm một chút. Alice và Bob có thể xác định tập hợp này trước khi thực hiện giao thức. Khi cần xâu ngẫu nhiên cho giao thức, Alice và Bob chỉ cần chọn ra một xâu trong tập hợp đó. Tập hợp này đủ nhỏ để việc xác định xâu nào được chọn chỉ đòi hỏi trao đổi một số nhỏ bit. Sau đây là chứng minh cụ thể.
Xét một giao thức "P" có xác suất sai không quá 0.1. Đặt formula_67 là tập hợp formula_89 xâu độ dài "n", ký hiệu là formula_90. Với một formula_67 cho trước, định nghĩa giao thức formula_92 như sau: Alice chọn formula_93, gửi "i" cho Bob, và sau đó hai người thực hiện "P" với xâu ngẫu nhiên công cộng là formula_93. Việc gửi "i" đòi hỏi gửi đi "O"(log 100"n") = "O"(log "n") bit.
Định nghĩa formula_95 and formula_96 là xác suất formula_97 và formula_92 tính được kết quả đúng cho dữ liệu vào formula_99.
Xét việc chọn các xâu trong formula_67 một cách ngẫu nhiên. Với một dữ liệu vào formula_99 cố định, theo bất đẳng thức Hoeffding:
Khi xét tất cả mọi bộ dữ liệu formula_99:
Bất đẳng thức cuối cùng ở trên là đúng vì có formula_23 bộ dữ liệu formula_99 khác nhau. Vì xác suất nhỏ hơn 1, nên tồn tại formula_107 sao cho formula_99:
Vì formula_97 có xác suất sai 0.1, nên formula_111 có xác suất sai không quá 0.2.