我們說一個通訊問題，是有兩台機器Alice和Bob，它們需要計算某個函數 f(x， y)。

　　但是Alice只知道輸入x，Bob只知道y。

　　它們之間離得很遠，需要通過光纜互相傳遞信息，把f(x， y)計算出來。

　　它們之間傳遞信息的過程稱為通訊，一個有效的通訊過程稱為一個協議。

　　舉一個例子，比如兩個數據中心，它們想知道它們的數據是否已經同步(指數據完全一樣)，如果不一樣的話就需要重新同步。

　　它們之間該怎麽通訊來確定這一點呢?這個問題就是通訊問題 EQ。

　　在這個問題裡，Alice和Bob分別擁有一個字符串x和y，它們想計算x==y。

　　對於所有通訊問題，Alice可以通過發送它的所有輸入x到Bob，然後Bob擁有全部輸入，從而計算f(x， y)。

　　注意在通訊問題裡面，我們隻考慮通訊消耗，而不考慮本地的計算時間和空間消耗。

　　我們能設計更好的通訊協議嗎?

　　對於一個通訊問題，如果要求對於任何輸入，輸出結果完全精確，這種符合條件的協議稱為確定型通訊協議。

　　但在實際應用中，我們可以容忍一個足夠小的出錯概率。

　　在某些時候這是有很大好處的。比如上面那個EQ通訊問題，在要求結果完全精確的情況下，Alice發送自己的x已經是一個最優方案了。

　　但在實際應用中，我們有一個更簡單的方法，那就是發送hash函數(比如MD5碼)，然後雙方檢驗MD5碼即可。

　　當然某種意義上這個協議不夠嚴格，更嚴格的應該是Alice隨機選擇一個合適長度的質數，然後發送。

　　複雜性的意思就是說一個問題能以多快的速度解決。

　　比如EQ的任何確定型通訊協議無法比發送所有輸入做得更好，這說明EQ的複雜度為O(n)。

　　類似於計算理論，人們發現證明一個複雜性比設計一個算法和協議更困難。