通信复杂度问题
通信復雜度問題:確定雙方手中所有數的中位數
????通信復雜度(communication complexity)主要研究這么一類問題: A 持有數據 x , B 持有數據 y ,他們想要合作計算某個關于 x 和 y 的二元函數值 f(x, y) ,那么在漸近意義下,兩人至少需要傳輸多少 bit 的數據。最近著迷于通信復雜度,看到了幾個與通信復雜度有關的問題,和大家分享一下。下面就是其中之一。
????A 、 B 的手中各有一個 {1, 2, …, n} 的子集。兩人想知道,如果把他們手中的數全都放在一塊兒,那么這些數(可能會有重復的數)的中位數是多少。然而, A 、 B 兩人遠隔千里,他們之間通信的成本非常高。因此,他們想在通信線路上傳輸盡可能少的信息,使得最終兩人都知道中位數的值。在這里,為了簡便起見,我們直接 定義 m 個數的中位數是第 ? m / 2 ? 小的數,因而如果 m = 2k ,那么中位數就應該直接取第 k 小的數。
????其中一種最笨的方法是, A 把手中的所有數全部發給 B 。由于發送一個不超過 n 的正整數最多會用到 log(n) 個 bit ,而 A 手里的數最多有 O(n) 個,因此 A 傳給 B 的信息量就是 O(n · logn) 。于是, B 就得到了足夠多的信息,可以直接計算中位數了,算好后再把結果告訴 A ,此時又要耗費 log(n) 個 bit (但它并不會成為通信量的瓶頸)。因此,在這種方案中,總的通信復雜度就是 O(n · logn) 。事實上,傳送一個 {1, 2, …, n} 的子集只需要一個 n 位 01 串就夠了,因而我們可以把通信復雜度降低到 O(n) 個 bit 。
????利用下面的辦法,我們可以實現 O(logn · logn) 的通信復雜度。首先, A 、 B 分別告訴對方自己手中有多少個數,這一共會耗費 O(logn) 個 bit 。接下來,兩人在區間 [1, n] 上進行二分查找。假設到了某一步,中位數被限定在了區間 [i, j] 里,那么 A 就計算出 k = (i + j) / 2 ,數一數自己手中有多少個數比 k 小,然后告訴 B ,由 B 再來數數自己這邊又有多少個比 k 小的數,從而判斷出 k 作為中位數來說是偏大了還是偏小了,并把判斷出來的結果返回給 A 。根據情況,區間 [i, j] 將被更新為 [i, k] 或者 [k, j] ,兩人在新的區間上繼續二分下去。整個算法將會持續 O(logn) 輪,每一輪都會傳輸 O(logn) 的數據,因此總的通信復雜度是 O(logn · logn) 。
????另一方面,通信復雜度至少是 Ω(logn) 的。這是因為,如果規定 A 和 B 最多只能交流 k 個 bit ,那么整個交流歷史最多就只有 k 次分岔的機會,到最后最多只能產生 2k 個不同的分支;但事實上中位數有可能是 1 到 n 中的任何一個,共有 n 種不同的可能,因此 2k 必須大于等于 n 。這說明 k 必須大于等于 log2(n) ,也就是說兩個人總會有必須要交流 log2(n) 個 bit 才行的時候。
????一個有意思的問題自然而然地誕生了:我們所得的上界和下界仍然有差距。究竟是剛才的算法還不夠經濟,還是剛才證明的結論還不夠強呢?
????還想說明一點的是,兩個人商量算法的過程,或者其中一個人把算法告訴另一個人的過程,這可以不算進通信復雜度里。事實上,把它們算進通信復雜度里也沒關系,因為它們反正都是 O(1) 的。
?
????我們還能把通信復雜度進一步降低到 O(logn) ,從而完美地解決這個問題。為此,我們先給出另一種 O(logn · logn) 的算法,然后把它改進到 O(logn) 去。
????假設 A 和 B 手中的數分別有 |A| 個和 |B| 個,而且正好有 |A| = |B| = 2k ,其中 k 是某個正整數。如果不是的話,可以讓 A 先花費 O(logn) 個 bit 把 |A| 告訴 B ,同樣地, B 也花費 O(logn) 個 bit 把 |B| 告訴 A 。然后,兩人找出一個最小的但是比 |A| 和 |B| 都大的 2k 。接下來,兩個人都在自己的數據當中加入 1 和 n ,把各自手中的數填充到 2k 個。只要最后兩個人總共加入了同樣多的 1 和 n (或者加進去的 n 比加進去的 1 多一個,如果 |A| + |B| 是奇數的話),這都不會改變中位數的值。兩人可以花費 O(logn) 個 bit 來約定,每個人都往自己的數據里加入多少個 1 和多少個 n 。注意,雖然兩個人手中的數變多了,但從對數意義上看,這僅僅是常數級別的變化。
????現在,每個人手中都有 2k 個數了。每個人都給自己手中的所有數從小到大排個序。假設此時 A 手中所有數的中位數是 a , B 手中所有數的中位數是 b 。兩人用 O(logn) 個 bit 交換 a 和 b 的值。如果 a < b ,那么 A 手中前面一半的數肯定不可能是中位數了, A 就把前面一半的數丟掉;同時, B 手中后面一半的數肯定也不可能是中位數,因此 B 就可以把他手中后面一半的數都丟掉。類似地,如果 a > b ,那么 A 就可以把他后面一半的數丟掉, B 就可以把他前面一半的數丟掉。不管怎么樣, A 、 B 兩人手里的數都只剩下原來的一半了,并且如果把兩個人手中的數合起來看,那么真正的中位數左右兩邊都被去掉了同樣多的數,因而剩下的數將會保持中位數不 變。接下來, A 算出新的 a 是多少, B 算出新的 b 是多少,然后兩人再次比較 a 和 b ,并繼續扔掉各自手里其中一半的數……不斷這樣做下去,那么每個人手中的數都會成半地減少。等到哪一步,兩個人手里都只剩一個數了,小的那個數一定就是中 位數了;或者某一步出現了 a = b 的情況,那么這個值就一定是中位數了。整個過程一共有 O(logn) 輪,每一輪都會傳輸 O(logn) 的數據,因此總的通信復雜度是 O(logn · logn) 。
????現在,我們把算法的通信復雜度改進到 O(logn) 。首先注意到,在每一輪當中,雙方并不需要知道 a 和 b 的值,只需要知道 a 和 b 誰更大一些。因此,兩個人可以從高到低輪流發送 a 和 b 的二進制位,一旦出現不同就可以立即停下來了。另外,如果這一輪逐位比較大小的時候,到了左起第 i 位才比出 a 和 b 的大小,那么對于今后的 a 和 b 來說,我們要么根本就不用比較,要么就可以直接從第 i 位開始比較。比方說,在這一輪里雙方發現 a = 00100????? 并且 b = 00101????? ,這就說明 a < b 。此時, A 會去掉前面一半的數,那些頭幾位就比 00100 小的數肯定都被去掉了,剩下的數只有可能以 00100, 00101, 00110, 00111, 01000, … 打頭;類似地, B 則會去掉后面一半的數,剩下的數只能以 00101, 00100, 00011, 00010, … 打頭。假如今后某一輪中的 a 值是以 00110 打頭的,那么 A 不用跟 B 說話就能直接知道,這回肯定是 a 值更大一些 ,因為 B 的手里不可能有這么大的數,它們都已經被去掉了。此時, A 就可以用 O(1) 個 bit 直接告訴 B ,這回我的 a 肯定比你的 b 大,咱倆該怎么辦就怎么辦吧。類似地,今后 B 也可能會出現這樣的情況:一看 b 值的頭幾位,直接就知道該怎么辦了。除非 a 和 b 都以 00100 或者 00101 打頭,我們才真的需要比較 a 和 b 的大小,因此我們可以直接從上次停止的數位開始繼續往下比。
????如果某一輪當中比到了相同的位,那么這些位今后就再也不用交換了,而 a 和 b 都有 O(logn) 位,這說明兩人一共交換了 O(logn) 次相同的位;如果某一輪當中比到了不同的位,那么這一輪比較就會立即停止,這說明每一輪里最多只會遇到一次不同的位,而整個算法有 O(logn) 輪,因而兩人一共也就交換了 O(logn) 次不同的位。另外,整個算法開始前會有 O(logn) 的交流(為了把數據填充到 2k 個),每一輪也會產生 O(1) 的交流(告訴對方是否需要比較)。因而,最終總的通信復雜度就是 O(logn) 。
參考資料: Eyal Kushilevitz and Noam Nisan, Communication complexity.
?
?
通訊復雜性簡單介紹
作者:張志強, 發表于 2008年9月17日
英文是communication complexity,不知道該翻譯成通信復雜性,還是通訊復雜性呢。這里先用通訊復雜性吧。這是一個理論計算機的子領域,在過去30年衍生了很多東西。它是我的研究的主要內容,這里簡略介紹一下。
1.Communication Protocol 通訊協議
我們說一個通訊問題,是有兩臺機器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隨機選擇一個合適長度的質數 p ,然后發送 (p,xmodp)
。
2.Communication Complexity 通訊復雜性
復雜性的意思就是說一個問題不能以多快的速度解決。比如EQ的任何確定型通訊協議無法比發送所有輸入做得更好,這說明EQ的復雜度為 O(n)
。類似于計算理論,人們發現證明一個復雜性比設計一個算法和協議更困難。
3.量子通訊復雜性
量子通訊和上面的經典通訊基本上是一樣的,除了Alice和Bob是兩臺量子計算機,可以操縱量子比特,以及它們之間共享量子通道可以發送量子比特。我們希望能夠盡可能少的發送量子比特就能解決問題。
就像在計算理論里,人們非常關系量子系統的引入能否大幅度提高計算的速度,人們也關心量子系統對于通訊的幫助。目前,人們發現對于partial函數(對于某些輸入對 (x,y)
, f(x,y) 可以沒有定義的 f 稱為partial函數),量子系統可以指數級的縮減發送的比特數,但對于完全函數(對 ?(x,y) , f(x,y)
都有定義),人們猜測量子系統是沒有幫助的。
4.通訊復雜性理論和信息論
通訊復雜性理論和信息論是兩個不同的領域。通訊復雜性通常研究如何發送盡可能少的比特得到計算結果,而信息論是研究通訊的過程(?),比如如何糾錯,如何利用量子糾纏等。現在的量子信息論發展非常火熱,但和量子通訊復雜性是兩個完全不同的概念。
5.GT 一個更復雜的例子
現在Alice和Bob分別擁有兩個字符串 x
和 y
,它們該如何確定誰的字符串更大(按字典序)呢?同樣這里很低的錯誤概率是可以忍受的。
思路:每次Alice和Bob先檢查前一半輸入是否相等(調用EQ的通訊協議),如果是,拋棄之;否則后一半可以拋棄;重復這個步驟即可。
Q.E.D.
?
?
?
總結
- 上一篇: storm基础系列之五---------
- 下一篇: 编译过程中,termcap.h