Độ 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 f(x,y) 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ố $f$: X $\times$ Y $\rightarrow$ Z trong đó ta giả sử $X=Y=\{0,1\}^{n}$ và $Z=\{0,1\}$. Alice nhận được dữ liệu vào là một xâu n-bit $x$ $\in$ X và Bob nhận được một xâu n-bit $y$ $\in$ 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 $f(x,y)$ 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 f, ký hiệu là $D(f)$, được định nghĩa là

$D(f)=$ số bit ít nhất Alice và Bob cần gửi trong trường hợp xấu nhất

Trong định nghĩa trên, nên xem $f$ là một ma trận $A$ (gọi là ma trận dữ liệu vào) trong đó mỗi hàng ứng với một giá trị $x$ $\in$ X và mỗi cột ứng với một $y$ $\in$ Y. Mỗi phần tử của ma trận dữ liệu vào $A_{\mathrm {x,y} }=f(x,y)$. 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 $f$). 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ả $x$ và $y$. Khi mới bắt đầu, bất kì một trong số $2^{2n}$ 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 $\subseteq$ X $\times$ Y được gọi là một hình chữ nhật (tổ hợp) nếu bất kì khi nào $(x_{1},y_{1})$ $\in$ R và $(x_{2},y_{2})$ $\in$ R thì $(x_{1},y_{2})$ $\in$ R. Một cách tương đương, R là một ma trận con của A sao cho R = M $\times$ N trong đó M $\subseteq$ X và N $\subseteq$ Y. Xét thời điểm hai người đã trao đổi $k$ bit. Với một giá trị cố định $h$ $\in$ $\{0,1\}^{k}$, định nghĩa

$T_{\mathrm {h} }=\{(x,y):h$ chính là k-bit được trao đổi khi dữ liệu vào là $(x,y)$}

Khi đó, $T_{\mathrm {h} }$ $\subseteq$ X $\times$ Y, và $T_{\mathrm {h} }$ 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 $x$ có bằng $y$. 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 $n$ bit trong trường hợp xấu nhất. Trước hết, xét ví dụ $x$ và $y$ 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 $x$, và các cột ứng với các giá trị của $y$.

EQ	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

Theo ma trận trên, hàm chỉ nhận giá trị 1 khi $x$ bằng $y$ (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 $y$ là 1, thì chỉ cần xem xét một nửa số cột (trong đó $y$ bằng 100, 101, 110, hoặc 111).

Định lý: $D(EQ)=n$.
Chứng minh. Giả sử cho mục đích phản chứng $D(EQ)\leq n-1$. Nghĩa là tồn tại hai bộ dữ liệu vào khác nhau $(x,x)$ và $(x',x')$ có cùng một lịch sử $h$. Vì mỗi lịch sử luôn xác định một hình chữ nhật, và $f(x,x)=f(x',x')=1$ nên $f(x,x')=1$. Theo giả thuyết $x\neq x'$ 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 $D(EQ)$ nhỏ hơn $n$, 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 $f$ 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 $R$ cho hàm $f$ 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.

$\Pr[R(x,y)=0]>{\frac {1}{2}},{\textrm {if}}\,f(x,y)=0$

$\Pr[R(x,y)=1]>{\frac {1}{2}},{\textrm {if}}\,f(x,y)=1$

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 $z\in \{0,1\}^{n}$. Alice tính $b=z\cdot x$ và gửi b cho Bob. Ký hiệu $(\cdot )$ là phép tính tích vô hướng trong GF(2). Sau đó Bob so sánh b với $z\cdot y$. 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 $x=y$, thì $z\cdot x=z\cdot y$, nên $Prob_{z}[$chấp nhận$]=1$. Nếu x không bằng y, vẫn có khả năng $z\cdot x=z\cdot y$, 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, $x_{i}=0$ và $y_{i}=1$. Với mọi xâu ngẫu nhiên z sao cho $z\cdot x=z\cdot y$, xét xâu z' giống hệt như z ngoại trừ vị trí thứ i. Khi đó, $z'\cdot x\neq z'\cdot y$. Vì vậy $Prob_{z}[$chấp nhận$]\leq 1/2$. 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 $EQ(x,y)$ 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 $n$-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 $R$ là tập hợp $100n$ xâu độ dài n, ký hiệu là $r_{1},r_{2},\dots ,r_{100n}$. Với một $R$ cho trước, định nghĩa giao thức $P'_{R}$ như sau: Alice chọn $r_{i}$, 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à $r_{i}$. Việc gửi i đòi hỏi gửi đi O(log 100n) = O(log n) bit.

Định nghĩa $p(x,y)$ and $p'_{R}(x,y)$ là xác suất $P$ và $P'_{R}$ tính được kết quả đúng cho dữ liệu vào $(x,y)$.

Xét việc chọn các xâu trong $R$ một cách ngẫu nhiên. Với một dữ liệu vào $(x,y)$ cố định, theo bất đẳng thức Hoeffding:

$\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}$

Khi xét tất cả mọi bộ dữ liệu $(x,y)$:

$\Pr _{R}[\exists (x,y):\,|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1$

Bất đẳng thức cuối cùng ở trên là đúng vì có $2^{2n}$ bộ dữ liệu $(x,y)$ khác nhau. Vì xác suất nhỏ hơn 1, nên tồn tại $R_{0}$ sao cho $(x,y)$:

$|p'_{R_{0}}(x,y)-p(x,y)|<0.1$

Vì $P$ có xác suất sai 0.1, nên $P'_{R_{0}}$ 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.

Tham khảo

• Kushilevitz, E.; Nisan, N. (1997), Communication complexity, Cambridge University Press
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005
• Dietzfelbinger, M.; Hromkovič, J.; Schnitger, G. (1996), “A comparison of two lower-bound methods for communication complexity”, Theoret. Comput. Sci., 168 (1): 39–51
• Raz, Ran (2004), “Circuit and Communication Complexity”, trong Rudich, Steven; Wigderson, Avi (biên tập), Computational Complexity Theory, American Mathematical Society Institute for Advanced Study, tr. 129–137
• Yao, A. C. (1979), “Some Complexity Questions Related to Distributed Computing”, Proc. of 11th STOC, tr. 209–213
• Newman, I. (1991), “Private vs. Common Random Bits in Communication Complexity”, Information Processing Letters, 39: 67–71