第525章 -pr方程

  我們說一個通訊問題，是有兩台機器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)。


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