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
Một cách diễn đạt khác của chứng minh trên là nếu formula_64 nhỏ hơn formula_47, ta luôn tìm được một hình chữ nhật trong ma trận EQ chứa nhiều hơn một ô trên đường chéo chính. Tất cả các ô trong hình chữ nhật đó đều phải bằng 1 thì Alice và Bob mới được phép tính ra giá trị 1. Tuy nhiên không tồn tại hình chữ nhật nào như vậy trong ma trận EQ.
Độ phức tạp truyền thông ngẫu nhiên.
Trong định nghĩa trên, giao thức là hoàn toàn đơn định và kết quả luôn chính xác. Nếu hai người được phép sử dụng các bit ngẫu nhiên và có một xác suất nhỏ tính ra kết quả sai, thì liệu họ có thể tính giá trị của formula_13 mà chỉ cần trao đổi ít thông tin hơn nhiều trường hợp trước? Yao
đã trả lời câu hỏi này bằng cách đưa ra khái niệm độ phức tạp truyền thông ngẫu nhiên.
Một giao thức ngẫu nhiên formula_67 cho hàm formula_13 với lỗi hai mặt thỏa mãn hai điều kiện sau với mọi "x" và "y" cố định.
Có thể xem một giao thức ngẫu nhiên và một giao thức đơn định có thêm một dữ liệu vào là một chuỗi các bit ngẫu nhiên. Có hai loại bit ngẫu nhiên khác nhau: "xâu ngẫu nhiên công cộng" là một xâu ngẫu nhiên cả Alice và Bob đều biết trước khi giao thức bắt đầu, trong khi "xâu ngẫu nhiên riêng" chỉ được cung cấp riêng cho mỗi người. Có một định lý khẳng định rằng bất kì một giao thức sử dụng xâu ngẫu nhiên công cộng nào đều có thể được giả lập bằng một giao thức sử dụng xâu ngẫu nhiên riêng với lượng bit cần trao đổi tăng thêm "O(log n)" bit.
Ghi chú là trong các điều kiện xác suất ở trên, kết quả "chỉ" phụ thuộc xâu ngẫu nhiên; cả hai xâu "x" và "y" đều nhận giá trị cố định. Nói cách khác, R(x,y) trả về giá trị g(x,y,r) khi sử dụng xâu ngẫu nhiên "r", và g(x,y,r) = f(x,y) với ít nhất một nửa số giá trị của "r".