✨Độ 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ố $f$: X $\backslash times$ Y $\backslash 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$ $\backslash in$ X và Bob nhận được một xâu n-bit $y$ $\backslash 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 , 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$ $\backslash in$ X và mỗi cột ứng với một $y$ $\backslash in$ Y. Mỗi phần tử của ma trận dữ liệu vào $A\_\{\backslash 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 $\backslash subseteq$ X $\backslash 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)$ $\backslash in$ R và $(x\_2,y\_2)$ $\backslash in$ R thì $(x\_1,y\_2)$ $\backslash in$ R. Một cách tương đương, R là một ma trận con của A sao cho R = M $\backslash times$ N trong đó M $\backslash subseteq$ X và N $\backslash subseteq$ Y. Xét thời điểm hai người đã trao đổi $k$ bit. Với một giá trị cố định $h$ $\backslash in$ $\{0,1\}^k$, định nghĩa

:$T\_\{\backslash 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 $\backslash subseteq$ X $\backslash 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$.

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)\; \backslash leq\; n-1$. Nghĩa là tồn tại hai bộ dữ liệu vào khác nhau $(x,\; x)$ và $(x\text{'},\; x\text{'})$ 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\text{'},\; x\text{'})\; =\; 1$ nên $f(x,\; x\text{'})=\; 1$. Theo giả thuyết $x\; \backslash neq\; x\text{'}$ 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. Độ 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