Độ 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.

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 . Alice tính  và gửi b cho Bob. Ký hiệu  là phép tính tích vô hướng trong GF(2). Sau đó Bob so sánh b với . 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 , thì , nên chấp nhận. Nếu x không bằng y, vẫn có khả năng , 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,  và . Với mọi xâu ngẫu nhiên z sao cho , xét xâu z' giống hệt như z ngoại trừ vị trí thứ i. Khi đó, . Vì vậy chấp nhận. 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  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.

Độ 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.