Độ phức tạp truyền thông

Khái niệm độ phức tạp truyền thông được đưa ra bởi Andrew Yao năm 1979,
khi nghiên cứu về việc hai người độc lập nhau (Alice và Bob) cùng cộng tác để thực hiện một công việc tính toán. Alice nhận được một xâu "n"-bit, ký hiệu là "x", và Bob nhận được một xâu "n"-bit khác, ký hiệu là "y". Mục tiêu là cuối cùng một trong hai người (ví dụ Bob) tính được giá trị một hàm sau khi hai người trao đổi một lượng thông tin ít nhất có thể. Ghi chú là ta không quan tâm đến số phép tính hay lượng bộ nhớ cần dùng. Độ phức tạp truyền thông là ngành nghiên cứu lượng thông tin cần truyền trong những bài toán tính toán phân tán như vậy.
Dĩ nhiên họ luôn đạt được mục tiêu bằng cách để Alice gửi toàn bộ xâu "n"-bit cô nhận được cho Bob, và sau đó Bob tính giá trị hàm số f, nhưng trong nhiều trường hợp, tùy vào hàm f, có thể giải quyết được bài toán với lượng bit cần trao đổi ít hơn n rất nhiều.
Bài toán trừu tượng này có nhiều ứng dụng: chẳng hạn trong thiết kế mạch VLSI, ta muốn cực tiểu hóa năng lượng cần dùng bằng cách giảm lượng tín hiệu điện cần gửi đi giữa các thành phần khác nhau trong quá trình tính toán. Bài toán này cũng có ứng dụng trong nghiên cứu cấu trúc dữ liệu, và tối ưu hóa mạng máy tính.
Định nghĩa.
Xét hàm số formula_1: X formula_2 Y formula_3 Z trong đó ta giả sử formula_4 và formula_5. Alice nhận được dữ liệu vào là một xâu n-bit formula_6 formula_7 X và Bob nhận được một xâu n-bit formula_8 formula_7 Y. Bằng cách gửi đi cho nhau mỗi lần 1 bit (theo một "giao thức truyền thông" nhất định), Alice và Bob muốn tính giá trị hàm formula_10 sao cho khi thực hiện xong, ít nhất một trong hai người biết giá trị của hàm. Dễ thấy sau khi một trong hai người biết kết quả thì chỉ cần người đó gửi kết quả cho người kia (bằng 1 bit) thì cả hai người đều biết kết quả. Độ phức tạp truyền thông xấu nhất của hàm , ký hiệu là formula_11, được định nghĩa là
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.
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).
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".
Độ 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.
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.
Độ phức tạp truyền thông lượng tử.
Độ phức tạp truyền thông lượng tử nghiên cứu việc sử dụng các hiệu ứng lượng tử để giảm lượng thông tin cần trao đổi trong tính toán phân tán.
Có ít nhất ba mô hình tổng quát hóa độ phức tạp truyền thông sử dụng lượng tử đã được đề xuất. Xem thêm bài toán tổng quan của G. Brassard.
Độ phức tạp truyền thông không đơn định.
Trong độ phức tạp truyền thông không đơn định, Alice và Bob được sử dụng máy tiên tri. Sau khi nhận được hướng dẫn của máy tiên tri, hai người trao đổi thông tin để tính "f(x,y)". Độ phức tạp truyền thông không đơn định được định nghĩa là tổng lớn nhất trong mọi giá trị "(x,y)" của số bit trao đổi giữa Alice và Bob cộng với số bit thông tin nhận được từ máy tiên tri.
Một cách định nghĩa khác là thông qua việc đếm số hình chữ nhật tổ hợp toàn 1 ít nhất cần dùng để phủ tất cả các phần tử một trong ma trận 0/1 của hàm cần tính . Độ phức tạp truyền thông không đơn định chính là lôgarit cơ số 2 của số hình chữ nhật tổ hợp toàn 1 ít nhất cần dùng để phủ tất cả các phần tử một trong ma trận.
Độ phức tạp truyền thông không đơn định là một cách để chặn dưới độ phức tạp truyền thông đơn định . Đồng thời, trong lý thuyết ma trận không âm, nó cũng được dùng làm chặn dưới của hạng không âm của một ma trận không âm.