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