計算理論（V）[共13頁]

《計算理論（V）[共13頁]》由會員分享，可在線閱讀，更多相關《計算理論（V）[共13頁]（13頁珍藏版）》請在裝配圖網上搜索。

1、計算理論(V)計算機學院陳翌佳姚期智Andrew Yao-2000年圖靈獎In recognition of hisfundamental contributions tothe theory of computation,including the complexity-basedtheory of pseudorandom numbergeneration,cryptography,andcommunication complexity.通訊復雜性 Communication Complexityy=1101011010 x=1100111010“x=y？”的通訊復雜性給定通訊雙方各自n位

2、2進制串x和y，他們需要交換多少位的信息才能判斷x是否等于y？定理.Yao,1979 判斷“x=y？”通訊雙方需要交換n位信息。通訊協議(protocol)的數學描述一個n位“x=y?”通訊協議P是一棵二叉樹，其中每個內部節點v包含一個函數w:0,1left,right或者l:0,1left,right；每個葉節點包含true,false中的一個值。給定x和y，通訊過程從樹的根開始：1.如果當前節點包含函數w，那么吳奇隆根據w(x)決定走向哪個兒子節點；2.如果當前節點包含函數l，那么劉詩詩根據l(x)決定走向哪個兒子節點;2.一旦到達葉節點，它所包含的true,false值就“x=y?”的結

3、果。通訊協議(protocol)的數學描述一個n位“x=y?”通訊協議P是一棵二叉樹，其中每個內部節點v包含一個函數w:0,1left,right或者l:0,1left,right；每個葉節點包含0,1中的一個值。通訊協議P的深度depth(P)，即最長的由根節點到某個葉節點的路徑長度，就是整個通訊要交換的信息總量。在所有計算“x=y?”的協議P中，我們想確定最小的depth(P)。通訊協議的組合特征對于協議P中的每個節點v，我們令Rv表示所有能夠到達v的(x,y)的集合。引理 1.所有葉節點的Rv構成了對0,10,1 的一個劃分。引理 2.每個葉節點的Rv都是0,10,1中的一個單色組合長方

4、形。組合長方形R0,10,1是一個組合長方形，當且僅當存在A,B0,1 使得R=AB。R0,10,1是單色的，當且僅當x=y對于所有的x,yR都成立，或者都不成立。組合長方形的等價刻畫引理.R0,10,1是一個組合長方形，當且僅當對于任意的(x,y)R和(x,y)R，我們有(x,y)R。通訊協議的組合特征引理 2.每個葉節點的Rv都是0,10,1中的一個單色組合長方形。證明.單色是顯然的。我們證明每個節點的Rv都是組合長方形。假設(x,y)Rv和(x,y)Rv，我們必須驗證(x,y)Rv。對v的深度歸納證明：從根節點出發到節點v，P的行為在(x,y),(x,y)和(x,y)上完全一致?！皒=y？”的通訊復雜性定理.Yao,1979 判斷“x=y？”通訊雙方需要交換n位信息。證明：-每個通訊協議P在0,10,1的對角線上需要2個單色長方形。-因此P至少有2個葉節點。-P的深度至少是n。