User Tools

Site Tools


31--ph-c-t-p-truy-n-th-ng-la-gi

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

31--ph-c-t-p-truy-n-th-ng-la-gi [2018/11/07 17:11] (current)
Line 1: Line 1:
 +<​HTML><​br><​div><​p>​Khái niệm <​b>​độ phức tạp truyền thông</​b>​ được đưa ra bởi Andrew Yao năm 1979,<​sup id="​cite_ref-yao1979_1-0"​ class="​reference">​[1]</​sup>​
 +khi nghiên cứu về việc hai người độc lập nhau (Alice và Bob) cùng cộng tác để thực hiện một công việc tính toán. Alice nhận được một xâu <​i>​n</​i>​-bit,​ ký hiệu là <​i>​x</​i>,​ và Bob nhận được một xâu <​i>​n</​i>​-bit khác, ký hiệu là <​i>​y</​i>​. Mục tiêu là cuối cùng một trong hai người (ví dụ Bob) tính được giá trị một hàm <span class="​texhtml">​f(<​i>​x</​i>,<​i>​y</​i>​)</​span>​ sau khi hai người trao đổi một lượng thông tin ít nhất có thể. Ghi chú là ta không quan tâm đến số phép tính hay lượng bộ nhớ cần dùng. Độ phức tạp truyền thông là ngành nghiên cứu lượng thông tin cần truyền trong những bài toán tính toán phân tán như vậy.
 +</​p><​p>​Dĩ nhiên họ luôn đạt được mục tiêu bằng cách để Alice gửi toàn bộ xâu <​i>​n</​i>​-bit cô nhận được cho Bob, và sau đó Bob tính giá trị hàm số f, nhưng trong nhiều trường hợp, tùy vào hàm f, có thể giải quyết được bài toán với lượng bit cần trao đổi ít hơn n rất nhiều.
 +</​p><​p>​Bài toán trừu tượng này có nhiều ứng dụng: chẳng hạn trong thiết kế mạch VLSI, ta muốn cực tiểu hóa năng lượng cần dùng bằng cách giảm lượng tín hiệu điện cần gửi đi giữa các thành phần khác nhau trong quá trình tính toán. Bài toán này cũng có ứng dụng trong nghiên cứu cấu trúc dữ liệu, và tối ưu hóa mạng máy tính.<​sup id="​cite_ref-Kushilevitz_1997_2-0"​ class="​reference">​[2]</​sup></​p>​
  
 +
 +
 +<​p>​Xét hàm số <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​132e57acb643253e7810ee9702d9581f159a1c61"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.279ex;​ height:​2.509ex;"​ alt="​{displaystyle f}"/></​span>:​ X <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle times }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​×<​!-- &times; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle times }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0ffafff1ad26cbe49045f19a67ce532116a32703"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ 0.019ex; margin-bottom:​ -0.19ex; width:​1.808ex;​ height:​1.509ex;"​ alt="​{displaystyle times }"/></​span>​ Y <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle rightarrow }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​→<​!-- &rarr; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle rightarrow }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​53e574cc3aa5b4bf5f3f5906caf121a378eef08b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​2.324ex;​ height:​1.843ex;"​ alt="​{displaystyle rightarrow }"/></​span>​ Z trong đó ta giả sử <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle X=Y={0,​1}^{n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​X</​mi><​mo>​=</​mo><​mi>​Y</​mi><​mo>​=</​mo><​mo fence="​false"​ stretchy="​false">​{</​mo><​mn>​0</​mn><​mo>,</​mo><​mn>​1</​mn><​msup><​mo fence="​false"​ stretchy="​false">​}</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​n</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle X=Y={0,​1}^{n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​4296f7f19168d97f188147be2a3c1d01fb85f4f8"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​16.852ex;​ height:​2.843ex;"​ alt="​{displaystyle X=Y={0,​1}^{n}}"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Z={0,​1}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​Z</​mi><​mo>​=</​mo><​mo fence="​false"​ stretchy="​false">​{</​mo><​mn>​0</​mn><​mo>,</​mo><​mn>​1</​mn><​mo fence="​false"​ stretchy="​false">​}</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Z={0,​1}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​2d8c1c3145420944ea12964a899c777236c614a5"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​10.463ex;​ height:​2.843ex;"​ alt="​{displaystyle Z={0,​1}}"/></​span>​. Alice nhận được dữ liệu vào là một xâu n-bit <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ X và Bob nhận được một xâu n-bit <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ Y. Bằng cách gửi đi cho nhau mỗi lần 1 bit (theo một <​i>​giao thức truyền thông</​i>​ nhất định), Alice và Bob muốn tính giá trị hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f(x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​29473ed0c4e838ac9dbe074535e507166c0e9101"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.607ex;​ height:​2.843ex;"​ alt="​{displaystyle f(x,​y)}"/></​span>​ sao cho khi thực hiện xong, ít nhất một trong hai người biết giá trị của hàm. Dễ thấy sau khi một trong hai người biết kết quả thì chỉ cần người đó gửi kết quả cho người kia (bằng 1 bit) thì cả hai người đều biết kết quả. Độ phức tạp truyền thông xấu nhất của hàm <span class="​texhtml">​f</​span>,​ ký hiệu là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle D(f)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​D</​mi><​mo stretchy="​false">​(</​mo><​mi>​f</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle D(f)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​9d5afbbd0e5cc5450dff4f0de2006936c4bc3acc"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.012ex;​ height:​2.843ex;"​ alt="​{displaystyle D(f)}"/></​span>,​ được định nghĩa là
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle D(f)=}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​D</​mi><​mo stretchy="​false">​(</​mo><​mi>​f</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo></​mstyle></​mrow>​{displaystyle D(f)=}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​9f3f9d34b452eb3f7e248151ab92eecc1249ec65"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.465ex;​ height:​2.843ex;"​ alt="​{displaystyle D(f)=}"/></​span>​ số bit ít nhất Alice và Bob cần gửi trong trường hợp xấu nhất</​dd></​dl><​p>​Trong định nghĩa trên, nên xem <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​132e57acb643253e7810ee9702d9581f159a1c61"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.279ex;​ height:​2.509ex;"​ alt="​f"/></​span>​ là một <a href="​http://​vi.wikipedia.org/​wiki/​Ma_tr%E1%BA%ADn"​ class="​mw-disambig"​ title="​Ma trận">​ma trận <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle A}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​A</​mi></​mstyle></​mrow>​{displaystyle A}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7daff47fa58cdfd29dc333def748ff5fa4c923e3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.743ex;​ height:​2.176ex;"​ alt="​A"/></​span>​ (gọi là <i>ma trận dữ liệu vào</​i>​) trong đó mỗi hàng ứng với một giá trị <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ X và mỗi cột ứng với một <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ Y. Mỗi phần tử của ma trận dữ liệu vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle A_{mathrm {x,y} }=f(x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​A</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mi mathvariant="​normal">​x</​mi><​mo>,</​mo><​mi mathvariant="​normal">​y</​mi></​mrow></​mrow></​msub><​mo>​=</​mo><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle A_{mathrm {x,y} }=f(x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​ca14fa49fa879d0846ecf63753e1a64f328642cf"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​13.874ex;​ height:​3.009ex;"​ alt="​{displaystyle A_{mathrm {x,y} }=f(x,​y)}"/></​span>​. Ban đầu cả Alice và Bob đều có một bản sao của toàn bộ ma trận A (giả sử cả hai người đều biết hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​132e57acb643253e7810ee9702d9581f159a1c61"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.279ex;​ height:​2.509ex;"​ alt="​f"/></​span>​). Khi đó, bài toán tính giá trị hàm số có thể xem là việc định vị giá trị cần tính trên ma trận. Bài toán này có thể giải được nếu Alice hoặc Bob biết cả <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​. Khi mới bắt đầu, bất kì một trong số <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle 2^{2n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msup><​mn>​2</​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn><​mi>​n</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle 2^{2n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​85543d7c2b7e0fea744a50af20d0f58b0f0fcfb3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​3.203ex;​ height:​2.676ex;"​ alt="​{displaystyle 2^{2n}}"/></​span>​ phần tử của ma trận đều có thể là giá trị cần tính. Sau đó sau mỗi lần một người gửi đi 1 bit cho người kia, một số hàng/cột bị loại đi và thu được một <a href="​http://​vi.wikipedia.org/​w/​index.php?​title=Ma_tr%E1%BA%ADn_con&​amp;​action=edit&​amp;​redlink=1"​ class="​new"​ title="​Ma trận con (trang chưa được viết)">​ma trận con của A.
 +</​p><​p>​Một tập hợp R <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle subseteq }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​⊆<​!-- &sube; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle subseteq }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a924f8dcb2847bb8871edfdbf4c6b5cca0669228"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​1.808ex;​ height:​2.176ex;"​ alt="​{displaystyle subseteq }"/></​span>​ X <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle times }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​×<​!-- &times; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle times }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0ffafff1ad26cbe49045f19a67ce532116a32703"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ 0.019ex; margin-bottom:​ -0.19ex; width:​1.808ex;​ height:​1.509ex;"​ alt="​{displaystyle times }"/></​span>​ Y được gọi là một <​i>​hình chữ nhật (tổ hợp)</​i>​ nếu bất kì khi nào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x_{1},​y_{1})}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​msub><​mi>​x</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​1</​mn></​mrow></​msub><​mo>,</​mo><​msub><​mi>​y</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​1</​mn></​mrow></​msub><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x_{1},​y_{1})}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7fc74086e56542bd28b46a84faaee3cebdd4a899"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.421ex;​ height:​2.843ex;"​ alt="​{displaystyle (x_{1},​y_{1})}"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ R và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x_{2},​y_{2})}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​msub><​mi>​x</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn></​mrow></​msub><​mo>,</​mo><​msub><​mi>​y</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn></​mrow></​msub><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x_{2},​y_{2})}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d52d44e16a796acee486af49af05f678566d181a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.421ex;​ height:​2.843ex;"​ alt="​{displaystyle (x_{2},​y_{2})}"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ R thì <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x_{1},​y_{2})}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​msub><​mi>​x</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​1</​mn></​mrow></​msub><​mo>,</​mo><​msub><​mi>​y</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn></​mrow></​msub><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x_{1},​y_{2})}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​64016788e4b5d1cdbadac009bf6b249fa423d580"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.421ex;​ height:​2.843ex;"​ alt="​{displaystyle (x_{1},​y_{2})}"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ R. Một cách tương đương, R là một ma trận con của A sao cho R = M <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle times }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​×<​!-- &times; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle times }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0ffafff1ad26cbe49045f19a67ce532116a32703"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ 0.019ex; margin-bottom:​ -0.19ex; width:​1.808ex;​ height:​1.509ex;"​ alt="​{displaystyle times }"/></​span>​ N trong đó M <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle subseteq }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​⊆<​!-- &sube; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle subseteq }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a924f8dcb2847bb8871edfdbf4c6b5cca0669228"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​1.808ex;​ height:​2.176ex;"​ alt="​{displaystyle subseteq }"/></​span>​ X và N <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle subseteq }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​⊆<​!-- &sube; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle subseteq }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a924f8dcb2847bb8871edfdbf4c6b5cca0669228"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​1.808ex;​ height:​2.176ex;"​ alt="​{displaystyle subseteq }"/></​span>​ Y. Xét thời điểm hai người đã trao đổi <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle k}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​k</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle k}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​c3c9a2c7b599b37105512c5d570edc034056dd40"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.211ex;​ height:​2.176ex;"​ alt="​k"/></​span>​ bit. Với một giá trị cố định <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle h}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​h</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle h}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b26be3e694314bc90c3215047e4a2010c6ee184a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.339ex;​ height:​2.176ex;"​ alt="​h"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle in }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​∈<​!-- &isin; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle in }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.55ex;​ height:​1.843ex;"​ alt="​in "/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle {0,​1}^{k}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo fence="​false"​ stretchy="​false">​{</​mo><​mn>​0</​mn><​mo>,</​mo><​mn>​1</​mn><​msup><​mo fence="​false"​ stretchy="​false">​}</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​k</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle {0,​1}^{k}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​336678931c6d9bfdbbc2062a2e523aa9c1c3a6ec"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.772ex;​ height:​3.176ex;"​ alt="​{displaystyle {0,​1}^{k}}"/></​span>,​ định nghĩa
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle T_{mathrm {h} }={(x,​y):​h}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​T</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mi mathvariant="​normal">​h</​mi></​mrow></​mrow></​msub><​mo>​=</​mo><​mo fence="​false"​ stretchy="​false">​{</​mo><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>:</​mo><​mi>​h</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle T_{mathrm {h} }={(x,​y):​h}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d74eb189db240ed9384d39b27310b749ec86d0b7"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​15.369ex;​ height:​2.843ex;"​ alt="​{displaystyle T_{mathrm {h} }={(x,​y):​h}"/></​span>​ chính là k-bit được trao đổi khi dữ liệu vào là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>​}</​dd></​dl><​p>​Khi đó, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle T_{mathrm {h} }}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​T</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mi mathvariant="​normal">​h</​mi></​mrow></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle T_{mathrm {h} }}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​052bde4363193801d53844d15a1b249e537f476e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​2.504ex;​ height:​2.509ex;"​ alt="​{displaystyle T_{mathrm {h} }}"/></​span>​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle subseteq }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​⊆<​!-- &sube; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle subseteq }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a924f8dcb2847bb8871edfdbf4c6b5cca0669228"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​1.808ex;​ height:​2.176ex;"​ alt="​{displaystyle subseteq }"/></​span>​ X <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle times }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo>​×<​!-- &times; --></​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle times }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0ffafff1ad26cbe49045f19a67ce532116a32703"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ 0.019ex; margin-bottom:​ -0.19ex; width:​1.808ex;​ height:​1.509ex;"​ alt="​{displaystyle times }"/></​span>​ Y,  và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle T_{mathrm {h} }}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​T</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mi mathvariant="​normal">​h</​mi></​mrow></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle T_{mathrm {h} }}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​052bde4363193801d53844d15a1b249e537f476e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​2.504ex;​ height:​2.509ex;"​ alt="​{displaystyle T_{mathrm {h} }}"/></​span>​ là một hình chữ nhật của A.
 +</​p><​p>​Dãy các bit được gửi đi giữa Alice và Bob được gọi là <​i>​lịch sử</​i>​ thực hiện của giao thức. Có thể xem quá trình thực hiện giao thức là như sau. Ban đầu tập hợp giá trị có thể là toàn bộ ma trận A. Ở mỗi bước, sau khi một bit được gửi đi, hai người thu hẹp được tập hợp các giá trị có thể thành một hình chữ nhật con của tập hợp giá trị ở bước trước. Cuối cùng khi toàn tất giao thức, tùy thuộc vào hình chữ nhật ở bước cuối cùng mà Alice và Bob quyết định giá trị hàm số là bao nhiêu. Nếu giao thức luôn tính đúng thì tất cả các phần tử của hình chữ nhật sau bước cuối cùng phải bằng nhau và Alice và Bob quyết định được giá trị cần tính chính là giá trị đó.
 +</p>
 +<​h3><​span id="​V.C3.AD_d.E1.BB.A5_h.C3.A0m_.C4.91.E1.BA.B3ng_th.E1.BB.A9c"/><​span class="​mw-headline"​ id="​Ví_dụ_hàm_đẳng_thức">​Ví dụ hàm đẳng thức</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=2"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Ví dụ hàm đẳng thức”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=2"​ title="​Sửa đổi phần “Ví dụ hàm đẳng thức”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Trong phần này, ta xét ví dụ trong đó Alice và Bob muốn xác định xem dữ liệu vào của họ có bằng nhau hay không. Nghĩa là ta muốn xác định xem <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ có bằng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​. Có thể chứng minh bài toán tính hàm đẳng thức (ký hiệu là EQ) luôn đòi hỏi trao đổi <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle n}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​n</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle n}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a601995d55609f2d9f5e233e36fbe9ea26011b3b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.395ex;​ height:​1.676ex;"​ alt="​n"/></​span>​ bit trong trường hợp xấu nhất.
 +Trước hết, xét ví dụ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ có 3 bit. Hàm đẳng thức được mô tả bởi ma trận dưới đây.Các hàng ứng với các giá trị của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>,​ và các cột ứng với các giá trị của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​.
 +</p>
 +<​center>​
 +<table border="​1"​ cellspacing="​0"​ cellpadding="​5"><​tbody><​tr><​td>​EQ
 +</td>
 +<​td>​000
 +</td>
 +<​td>​001
 +</td>
 +<​td>​010
 +</td>
 +<​td>​011
 +</td>
 +<​td>​100
 +</td>
 +<​td>​101
 +</td>
 +<​td>​110
 +</td>
 +<​td>​111
 +</​td></​tr><​tr><​td>​000
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​001
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​010
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​011
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​100
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​101
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​110
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</td>
 +<td>0
 +</​td></​tr><​tr><​td>​111
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>0
 +</td>
 +<td>1
 +</​td></​tr></​tbody></​table></​center>​
 +<​p>​Theo ma trận trên, hàm chỉ nhận giá trị 1 khi <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt="​x"/></​span>​ bằng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ (các phần tử trên đường chéo chính). Có thể nhận thấy việc gửi đi 1 bit dữ liệu vào giảm số khả năng đi 2 lần. Chẳng hạn, nếu ta biết bit đầu tiên của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ là 1, thì chỉ cần xem xét một nửa số cột (trong đó <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt="​y"/></​span>​ bằng 100, 101, 110, hoặc 111).
 +</​p><​p><​b>​Định lý: <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle D(EQ)=n}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​D</​mi><​mo stretchy="​false">​(</​mo><​mi>​E</​mi><​mi>​Q</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mi>​n</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle D(EQ)=n}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​96d1f555a725fdbe8af4e74f18984ad3da2002ff"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​11.841ex;​ height:​2.843ex;"​ alt="​{displaystyle D(EQ)=n}"/></​span>​.</​b><​br/>​Chứng minh. Giả sử cho mục đích phản chứng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle D(EQ)leq n-1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​D</​mi><​mo stretchy="​false">​(</​mo><​mi>​E</​mi><​mi>​Q</​mi><​mo stretchy="​false">​)</​mo><​mo>​≤<​!-- &le; --></​mo><​mi>​n</​mi><​mo>​−<​!-- &minus; --></​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle D(EQ)leq n-1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0aede6c5fda41531b0562f751a206da8bbefc8aa"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​15.844ex;​ height:​2.843ex;"​ alt="​{displaystyle D(EQ)leq n-1}"/></​span>​. Nghĩa là tồn tại hai bộ dữ liệu vào khác nhau <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​x)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​x</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​x)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​72f9e25892f6d000349b8bb6578a59567efbdd63"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.503ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​x)}"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x',​x'​)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup><​mo>,</​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x',​x'​)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​dfc3f52aed3ed3ea5dfa85cfb0533241551cbeb2"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.872ex;​ height:​3.009ex;"​ alt="​{displaystyle (x',​x'​)}"/></​span>​ có cùng một lịch sử <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle h}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​h</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle h}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b26be3e694314bc90c3215047e4a2010c6ee184a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.339ex;​ height:​2.176ex;"​ alt="​h"/></​span>​. Vì mỗi lịch sử luôn xác định một hình chữ nhật, và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(x,​x)=f(x',​x'​)=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​x</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup><​mo>,</​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f(x,​x)=f(x',​x'​)=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d56cfbd9dc5eff68e376ff0f8514a29a62bdad70"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​22.291ex;​ height:​3.009ex;"​ alt="​{displaystyle f(x,​x)=f(x',​x'​)=1}"/></​span>​ nên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(x,​x'​)=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f(x,​x'​)=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​5a5595662c2c790bb5aaada6e58258829f87da38"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​11.727ex;​ height:​3.009ex;"​ alt="​{displaystyle f(x,​x'​)=1}"/></​span>​. Theo giả thuyết <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle xneq x'​}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi><​mo>​≠<​!-- &ne; --></​mo><​msup><​mi>​x</​mi><​mo>​′</​mo></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle xneq x'​}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​2c6cfab4b1bd197bfe3d7b6ff190cd3ae73f0368"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.443ex;​ height:​3.009ex;"​ alt="​{displaystyle xneq x'​}"/></​span>​ nên giá trị đúng của hàm đẳng thức phải là 0 (mâu thuẫn).
 +</​p><​p>​Một cách diễn đạt khác của chứng minh trên là nếu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle D(EQ)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​D</​mi><​mo stretchy="​false">​(</​mo><​mi>​E</​mi><​mi>​Q</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle D(EQ)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​2da07d8d2cfae77b3f18107ecfd4ea534c0dd226"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.348ex;​ height:​2.843ex;"​ alt="​{displaystyle D(EQ)}"/></​span>​ nhỏ hơn <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle n}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​n</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle n}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a601995d55609f2d9f5e233e36fbe9ea26011b3b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.395ex;​ height:​1.676ex;"​ alt="​n"/></​span>,​ ta luôn tìm được một hình chữ nhật trong ma trận EQ chứa nhiều hơn một ô trên đường chéo chính. Tất cả các ô trong hình chữ nhật đó đều phải bằng 1 thì Alice và Bob mới được phép tính ra giá trị 1. Tuy nhiên không tồn tại hình chữ nhật nào như vậy trong ma trận EQ.
 +</p>
 +<​h2><​span id="​.C4.90.E1.BB.99_ph.E1.BB.A9c_t.E1.BA.A1p_truy.E1.BB.81n_th.C3.B4ng_ng.E1.BA.ABu_nhi.C3.AAn"/><​span class="​mw-headline"​ id="​Độ_phức_tạp_truyền_thông_ngẫu_nhiên">​Độ phức tạp truyền thông ngẫu nhiên</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=3"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Độ phức tạp truyền thông ngẫu nhiên”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=3"​ title="​Sửa đổi phần “Độ phức tạp truyền thông ngẫu nhiên”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​Trong định nghĩa trên, giao thức là hoàn toàn đơn định và kết quả luôn chính xác. Nếu hai người được phép sử dụng các bit ngẫu nhiên và có một xác suất nhỏ tính ra kết quả sai, thì liệu họ có thể tính giá trị của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​132e57acb643253e7810ee9702d9581f159a1c61"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.279ex;​ height:​2.509ex;"​ alt="​f"/></​span>​ mà chỉ cần trao đổi ít thông tin hơn nhiều trường hợp trước? Yao<sup id="​cite_ref-yao1979_1-1"​ class="​reference">​[1]</​sup>​
 +đã trả lời câu hỏi này bằng cách đưa ra khái niệm độ phức tạp truyền thông ngẫu nhiên.
 +</​p><​p>​Một giao thức ngẫu nhiên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle R}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​R</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle R}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​4b0bfb3769bf24d80e15374dc37b0441e2616e33"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.764ex;​ height:​2.176ex;"​ alt="​R"/></​span>​ cho hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​132e57acb643253e7810ee9702d9581f159a1c61"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.279ex;​ height:​2.509ex;"​ alt="​f"/></​span>​ với lỗi hai mặt thỏa mãn hai điều kiện sau với mọi <​i>​x</​i>​ và <​i>​y</​i>​ cố định.
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Pr[R(x,​y)=0]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=0}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo movablelimits="​true"​ form="​prefix">​Pr</​mo><​mo stretchy="​false">​[</​mo><​mi>​R</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​0</​mn><​mo stretchy="​false">​]</​mo><​mo>&​gt;</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mfrac><​mn>​1</​mn><​mn>​2</​mn></​mfrac></​mrow><​mo>,</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mtext>​if</​mtext></​mrow></​mrow><​mspace width="​thinmathspace"/><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​0</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Pr[R(x,​y)=0]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=0}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​3eb73d64efc3c9977401db0272a0f61e1e5ca6b4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.838ex; width:​33.886ex;​ height:​5.176ex;"​ alt="​{displaystyle Pr[R(x,​y)=0]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=0}"/></​span></​dd></​dl><​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Pr[R(x,​y)=1]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo movablelimits="​true"​ form="​prefix">​Pr</​mo><​mo stretchy="​false">​[</​mo><​mi>​R</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​1</​mn><​mo stretchy="​false">​]</​mo><​mo>&​gt;</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mfrac><​mn>​1</​mn><​mn>​2</​mn></​mfrac></​mrow><​mo>,</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mtext>​if</​mtext></​mrow></​mrow><​mspace width="​thinmathspace"/><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Pr[R(x,​y)=1]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​40ba81bdffdeab5911e1debfaf11a208e760e1da"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.838ex; width:​33.886ex;​ height:​5.176ex;"​ alt="​{displaystyle Pr[R(x,​y)=1]&​gt;​{frac {1}{2}},​{textrm {if}},​f(x,​y)=1}"/></​span></​dd></​dl><​p>​Có thể xem một giao thức ngẫu nhiên và một giao thức đơn định có thêm một dữ liệu vào là một chuỗi các bit ngẫu nhiên. Có hai loại bit ngẫu nhiên khác nhau: <​i>​xâu ngẫu nhiên công cộng</​i>​ là một xâu ngẫu nhiên cả Alice và Bob đều biết trước khi giao thức bắt đầu, trong khi <​i>​xâu ngẫu nhiên riêng</​i>​ chỉ được cung cấp riêng cho mỗi người. Có một định lý khẳng định rằng bất kì một giao thức sử dụng xâu ngẫu nhiên công cộng nào đều có thể được giả lập bằng một giao thức sử dụng xâu ngẫu nhiên riêng với lượng bit cần trao đổi tăng thêm <​i>​O(log n)</​i>​ bit.
 +</​p><​p>​Ghi chú là trong các điều kiện xác suất ở trên, kết quả  <​i>​chỉ</​i>​ phụ thuộc xâu ngẫu nhiên; cả hai xâu <​i>​x</​i>​ và <​i>​y</​i>​ đều nhận giá trị cố định. Nói cách khác, R(x,y) trả về giá trị g(x,y,r) khi sử dụng xâu ngẫu nhiên <​i>​r</​i>,​ và g(x,y,r) = f(x,y) với ít nhất một nửa số giá trị của <​i>​r</​i>​.
 +</​p><​p>​Độ phức tạp ngẫu nhiên được định nghĩa là số bit cần trao đổi trong trường hợp xấu nhất của giao thức.
 +</​p><​p>​Cũng có thể định nghĩa giao thức ngẫu nhiên với lỗi một mặt một cách tương tự.
 +</p>
 +<​h3><​span id="​Giao_th.E1.BB.A9c_ng.E1.BA.ABu_nhi.C3.AAn_cho_v.C3.AD_d.E1.BB.A5_EQ"/><​span class="​mw-headline"​ id="​Giao_thức_ngẫu_nhiên_cho_ví_dụ_EQ">​Giao thức ngẫu nhiên cho ví dụ EQ</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=4"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Giao thức ngẫu nhiên cho ví dụ EQ”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=4"​ title="​Sửa đổi phần “Giao thức ngẫu nhiên cho ví dụ EQ”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Quay lại với ví dụ <​i>​EQ</​i>,​ nếu được phép có lỗi, thì Alice và Bob có thể kiểm tra đẳng thức bằng cách trao đổi <​i>​O(log n)</​i>​ bit. Xét giao thức sau:  giả sử Alice và Bob đều biết một xâu ngẫu nhiên công cộng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle zin {0,​1}^{n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​z</​mi><​mo>​∈<​!-- &isin; --></​mo><​mo fence="​false"​ stretchy="​false">​{</​mo><​mn>​0</​mn><​mo>,</​mo><​mn>​1</​mn><​msup><​mo fence="​false"​ stretchy="​false">​}</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​n</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle zin {0,​1}^{n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​fb46c063f5d38bf3b59d6707dbcec5094facdacf"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​10.831ex;​ height:​2.843ex;"​ alt="​{displaystyle zin {0,​1}^{n}}"/></​span>​. Alice tính <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle b=zcdot x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​b</​mi><​mo>​=</​mo><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​x</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle b=zcdot x}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b932448e358016dd752b9da639b53122e1fd627a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​8.193ex;​ height:​2.176ex;"​ alt="​{displaystyle b=zcdot x}"/></​span>​ và gửi <​i>​b</​i>​ cho Bob. Ký hiệu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (cdot )}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mo>​⋅<​!-- &sdot; --></​mo><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (cdot )}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a4c2b509ce21093c430b9c0849fa1aef7f0f1d24"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​2.456ex;​ height:​2.843ex;"​ alt="​{displaystyle (cdot )}"/></​span>​ là phép tính <a href="​http://​vi.wikipedia.org/​wiki/​T%C3%ADch_v%C3%B4_h%C6%B0%E1%BB%9Bng"​ title="​Tích vô hướng">​tích vô hướng</​a>​ trong GF(2). Sau đó Bob so sánh <​i>​b</​i>​ với <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle zcdot y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle zcdot y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0fb8e86afafa54396111bb40ef2ccc2616f80875"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​3.923ex;​ height:​2.009ex;"​ alt="​{displaystyle zcdot y}"/></​span>​. Nếu chúng bằng nhau, thì Bob chấp nhận, đưa ra kết quả <​i>​x</​i>​ bằng <​i>​y</​i>​. Nếu không, Bob từ chối.
 +</​p><​p>​Rõ ràng, nếu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x=y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​x</​mi><​mo>​=</​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x=y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​409a91214d63eabe46ec10ff3cbba689ab687366"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​5.584ex;​ height:​2.009ex;"​ alt="​{displaystyle x=y}"/></​span>,​ thì <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle zcdot x=zcdot y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​x</​mi><​mo>​=</​mo><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle zcdot x=zcdot y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a996a819311abf92b2cb9811c582cb70ad67ad41"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​11.118ex;​ height:​2.009ex;"​ alt="​{displaystyle zcdot x=zcdot y}"/></​span>,​ nên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Prob_{z}[}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​P</​mi><​mi>​r</​mi><​mi>​o</​mi><​msub><​mi>​b</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​z</​mi></​mrow></​msub><​mo stretchy="​false">​[</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Prob_{z}[}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6cd6d66389fc7d51c21d4730368a64313e2380c7"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.568ex;​ height:​2.843ex;"​ alt="​{displaystyle Prob_{z}[}"/></​span>​chấp nhận<​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle ]=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​]</​mo><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle ]=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6347ecda470ded6377b5d2352646c479facd6133"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​4.263ex;​ height:​2.843ex;"​ alt="​{displaystyle ]=1}"/></​span>​. Nếu <​i>​x</​i>​ không bằng <​i>​y</​i>,​ vẫn có khả năng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle zcdot x=zcdot y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​x</​mi><​mo>​=</​mo><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle zcdot x=zcdot y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a996a819311abf92b2cb9811c582cb70ad67ad41"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​11.118ex;​ height:​2.009ex;"​ alt="​{displaystyle zcdot x=zcdot y}"/></​span>,​ dẫn đến việc Bob đưa ra câu trả lời sai.
 +</​p><​p>​Nếu <​i>​x</​i>​ và <​i>​y</​i>​ khác nhau, tồn tại ít nhất một vị trí chúng khác nhau. Không mất tính tổng quát, giả sử tại vị trí thứ <​i>​i</​i>,​ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x_{i}=0}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​x</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​i</​mi></​mrow></​msub><​mo>​=</​mo><​mn>​0</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle x_{i}=0}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​491e215fe273840aab63acab32e73cb14f2fc8e8"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​6.39ex;​ height:​2.509ex;"​ alt="​{displaystyle x_{i}=0}"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y_{i}=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​y</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​i</​mi></​mrow></​msub><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle y_{i}=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​13864bfc60110b9306a50b300d2d72b22fa1e371"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​6.2ex;​ height:​2.509ex;"​ alt="​{displaystyle y_{i}=1}"/></​span>​. Với mọi xâu ngẫu nhiên <​i>​z</​i>​ sao cho  <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle zcdot x=zcdot y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​x</​mi><​mo>​=</​mo><​mi>​z</​mi><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle zcdot x=zcdot y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a996a819311abf92b2cb9811c582cb70ad67ad41"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​11.118ex;​ height:​2.009ex;"​ alt="​{displaystyle zcdot x=zcdot y}"/></​span>,​ xét xâu <​i>​z'​ </i> giống hệt như <​i>​z</​i>​ ngoại trừ vị trí thứ <​i>​i</​i>​. Khi đó, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle z'cdot xneq z'cdot y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msup><​mi>​z</​mi><​mo>​′</​mo></​msup><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​x</​mi><​mo>​≠<​!-- &ne; --></​mo><​msup><​mi>​z</​mi><​mo>​′</​mo></​msup><​mo>​⋅<​!-- &sdot; --></​mo><​mi>​y</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle z'cdot xneq z'cdot y}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​046000e1288bfeb4f9fc4985af6c24ecf423c298"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​12.492ex;​ height:​3.009ex;"​ alt="​{displaystyle z'cdot xneq z'cdot y}"/></​span>​. Vì vậy <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Prob_{z}[}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​P</​mi><​mi>​r</​mi><​mi>​o</​mi><​msub><​mi>​b</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​z</​mi></​mrow></​msub><​mo stretchy="​false">​[</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Prob_{z}[}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6cd6d66389fc7d51c21d4730368a64313e2380c7"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.568ex;​ height:​2.843ex;"​ alt="​{displaystyle Prob_{z}[}"/></​span>​chấp nhận<​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle ]leq 1/​2}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​]</​mo><​mo>​≤<​!-- &le; --></​mo><​mn>​1</​mn><​mrow class="​MJX-TeXAtom-ORD"><​mo>/</​mo></​mrow><​mn>​2</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle ]leq 1/​2}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6f351c1b2cc69caaf61db1bbad1653e4737aa568"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.588ex;​ height:​2.843ex;"​ alt="​{displaystyle ]leq 1/​2}"/></​span>​. Giao thức này có thể được lặp lại nhiều lần để giảm xác suất sai.
 +</​p><​p>​Như vậy <​i>​nếu Alice và Bob có chung một xâu ngẫu nhiên công cộng n bit</​i>,​ họ có thể tính được <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle EQ(x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​E</​mi><​mi>​Q</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle EQ(x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​e47a70582d9aa3fdc04ab203deef7e5804c95d66"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.942ex;​ height:​2.843ex;"​ alt="​{displaystyle EQ(x,​y)}"/></​span>​ chỉ bằng việc gửi đi 1 bit. Trong phần dưới đây, ta sẽ xét một phương pháp giả lập một giao thức dùng <​i>​O(n)</​i>​ bit ngẫu nhiên công cộng bằng một giao thức với xâu ngẫu nhiên riêng với số bit cần trao đổi tăng thêm <​i>​O(log n)</​i>​ bit. Như vậy, tồn tại giao thức sử dụng xâu ngẫu nhiên riêng cho <​i>​EQ</​i>​ chỉ trao đổi <​i>​O(log n)</​i>​ bit.
 +</p>
 +<​h3><​span id="​Ng.E1.BA.ABu_nhi.C3.AAn_c.C3.B4ng_c.E1.BB.99ng_v.C3.A0_ri.C3.AAng"/><​span class="​mw-headline"​ id="​Ngẫu_nhiên_công_cộng_và_riêng">​Ngẫu nhiên công cộng và riêng</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=5"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Ngẫu nhiên công cộng và riêng”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=5"​ title="​Sửa đổi phần “Ngẫu nhiên công cộng và riêng”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Rõ ràng các bit ngẫu nhiên công cộng làm cho việc trao đổi thông tin dễ dàng hơn. Tuy nhiên, vẫn có thể sử dụng các giao thức dùng bit ngẫu nhiên công cộng ngay cả khi không có các bit này mà chỉ cần trao đổi thêm một số nhỏ bit. Mọi giao thức sử dụng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle n}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​n</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle n}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a601995d55609f2d9f5e233e36fbe9ea26011b3b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.395ex;​ height:​1.676ex;"​ alt="​n"/></​span>​-bit ngẫu nhiên công cộng đều có thể giả lập bằng việc trao đổi <​i>​O(log n)</​i>​ bit.
 +</​p><​p>​Một cách trực giác, ta tìm một tập hợp nhỏ các xâu có đủ độ ngẫu nhiên sao cho khi thực hiện giao thức ngẫu nhiên trên tập nhỏ này, xác suất sai chỉ tăng thêm một chút. Alice và Bob có thể xác định tập hợp này trước khi thực hiện giao thức. Khi cần xâu ngẫu nhiên cho giao thức, Alice và Bob chỉ cần chọn ra một xâu trong tập hợp đó. Tập hợp này đủ nhỏ để việc xác định xâu nào được chọn chỉ đòi hỏi trao đổi một số nhỏ bit. Sau đây là chứng minh cụ thể.
 +</​p><​p>​Xét một giao thức <​i>​P</​i>​ có xác suất sai không quá 0.1. Đặt <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle R}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​R</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle R}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​4b0bfb3769bf24d80e15374dc37b0441e2616e33"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.764ex;​ height:​2.176ex;"​ alt="​R"/></​span>​ là tập hợp <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle 100n}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mn>​100</​mn><​mi>​n</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle 100n}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​5ef4cb62b44e80bb9945558cf881737c947356f9"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​4.882ex;​ height:​2.176ex;"​ alt="​{displaystyle 100n}"/></​span>​ xâu độ dài <​i>​n</​i>,​ ký hiệu là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r_{1},​r_{2},​dots ,​r_{100n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​r</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​1</​mn></​mrow></​msub><​mo>,</​mo><​msub><​mi>​r</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn></​mrow></​msub><​mo>,</​mo><​mo>​…<​!-- &​hellip;​ --></​mo><​mo>,</​mo><​msub><​mi>​r</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​100</​mn><​mi>​n</​mi></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle r_{1},​r_{2},​dots ,​r_{100n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8cc325bf0753bb609e5f1202d736f423984a5f8e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​15.151ex;​ height:​2.009ex;"​ alt="​{displaystyle r_{1},​r_{2},​dots ,​r_{100n}}"/></​span>​. Với một <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle R}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​R</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle R}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​4b0bfb3769bf24d80e15374dc37b0441e2616e33"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.764ex;​ height:​2.176ex;"​ alt="​R"/></​span>​ cho trước, định nghĩa giao thức <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle P'​_{R}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msubsup><​mi>​P</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle P'​_{R}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​c8ac3ebf79e9296278d85a5c8dfe8d52f5fce723"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​2.972ex;​ height:​2.843ex;"​ alt="​{displaystyle P'​_{R}}"/></​span>​ như sau: Alice chọn <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r_{i}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​r</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​i</​mi></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle r_{i}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a0b6d651eaf432dbf1f106021c8bb499ae83fd1f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.848ex;​ height:​2.009ex;"​ alt="​{displaystyle r_{i}}"/></​span>,​ gửi <​i>​i</​i>​ cho Bob, và sau đó hai người thực hiện <​i>​P</​i>​ với xâu ngẫu nhiên công cộng là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r_{i}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​r</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​i</​mi></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle r_{i}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a0b6d651eaf432dbf1f106021c8bb499ae83fd1f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.848ex;​ height:​2.009ex;"​ alt="​{displaystyle r_{i}}"/></​span>​. Việc gửi <​i>​i</​i>​ đòi hỏi gửi đi <​i>​O</​i>​(log 100<​i>​n</​i>​) = <​i>​O</​i>​(log <​i>​n</​i>​) bit.
 +</​p><​p>​Định nghĩa <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle p(x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​p</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle p(x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​089e91a1824e14cebc8e8d04dc652c61b3008e0a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; margin-left:​ -0.089ex; width:​6.587ex;​ height:​2.843ex;"​ alt="​{displaystyle p(x,​y)}"/></​span>​ and <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle p'​_{R}(x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msubsup><​mi>​p</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle p'​_{R}(x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​627ad41c312a05aaaf795151aa36ba67a8c15c06"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; margin-left:​ -0.089ex; width:​8.067ex;​ height:​3.009ex;"​ alt="​{displaystyle p'​_{R}(x,​y)}"/></​span>​ là xác suất <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle P}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​P</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle P}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b4dc73bf40314945ff376bd363916a738548d40a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.745ex;​ height:​2.176ex;"​ alt="​P"/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle P'​_{R}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msubsup><​mi>​P</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle P'​_{R}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​c8ac3ebf79e9296278d85a5c8dfe8d52f5fce723"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​2.972ex;​ height:​2.843ex;"​ alt="​{displaystyle P'​_{R}}"/></​span>​ tính được kết quả đúng cho dữ liệu vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>​.
 +</​p><​p>​Xét việc chọn các xâu trong <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle R}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​R</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle R}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​4b0bfb3769bf24d80e15374dc37b0441e2616e33"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.764ex;​ height:​2.176ex;"​ alt="​R"/></​span>​ một cách ngẫu nhiên. Với một dữ liệu vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>​ cố định, theo <a href="​http://​vi.wikipedia.org/​wiki/​B%E1%BA%A5t_%C4%91%E1%BA%B3ng_th%E1%BB%A9c_Hoeffding"​ title="​Bất đẳng thức Hoeffding">​bất đẳng thức Hoeffding</​a>:​
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq 2exp(-2(0.1)^{2}cdot 100n)&​lt;​2^{-2n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​munder><​mo movablelimits="​true"​ form="​prefix">​Pr</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow></​munder><​mo stretchy="​false">​[</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​msubsup><​mi>​p</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​−<​!-- &minus; --></​mo><​mi>​p</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​mo>​≥<​!-- &ge; --></​mo><​mn>​0.1</​mn><​mo stretchy="​false">​]</​mo><​mo>​≤<​!-- &le; --></​mo><​mn>​2</​mn><​mi>​exp</​mi><​mo>​⁡<​!-- &#8289; --></​mo><​mo stretchy="​false">​(</​mo><​mo>​−<​!-- &minus; --></​mo><​mn>​2</​mn><​mo stretchy="​false">​(</​mo><​mn>​0.1</​mn><​msup><​mo stretchy="​false">​)</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn></​mrow></​msup><​mo>​⋅<​!-- &sdot; --></​mo><​mn>​100</​mn><​mi>​n</​mi><​mo stretchy="​false">​)</​mo><​mo>&​lt;</​mo><​msup><​mn>​2</​mn><​mrow class="​MJX-TeXAtom-ORD"><​mo>​−<​!-- &minus; --></​mo><​mn>​2</​mn><​mi>​n</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq 2exp(-2(0.1)^{2}cdot 100n)&​lt;​2^{-2n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​45f8000f9397f6ab452081c1b118ba696e24e5d0"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -2.005ex; width:​61.424ex;​ height:​4.343ex;"​ alt="​{displaystyle Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq 2exp(-2(0.1)^{2}cdot 100n)&​lt;​2^{-2n}}"/></​span></​dd></​dl><​p>​Khi xét tất cả mọi bộ dữ liệu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>:​
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Pr _{R}[exists (x,​y):,​|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq sum _{(x,y)}Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]&​lt;​sum _{(x,​y)}2^{-2n}=1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​munder><​mo movablelimits="​true"​ form="​prefix">​Pr</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow></​munder><​mo stretchy="​false">​[</​mo><​mi mathvariant="​normal">​∃<​!-- &exist; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>:</​mo><​mspace width="​thinmathspace"/><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​msubsup><​mi>​p</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​−<​!-- &minus; --></​mo><​mi>​p</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​mo>​≥<​!-- &ge; --></​mo><​mn>​0.1</​mn><​mo stretchy="​false">​]</​mo><​mo>​≤<​!-- &le; --></​mo><​munder><​mo>​∑<​!-- &sum; --></​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mrow></​munder><​munder><​mo movablelimits="​true"​ form="​prefix">​Pr</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow></​munder><​mo stretchy="​false">​[</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​msubsup><​mi>​p</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​R</​mi></​mrow><​mo>​′</​mo></​msubsup><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​−<​!-- &minus; --></​mo><​mi>​p</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​mo>​≥<​!-- &ge; --></​mo><​mn>​0.1</​mn><​mo stretchy="​false">​]</​mo><​mo>&​lt;</​mo><​munder><​mo>​∑<​!-- &sum; --></​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mrow></​munder><​msup><​mn>​2</​mn><​mrow class="​MJX-TeXAtom-ORD"><​mo>​−<​!-- &minus; --></​mo><​mn>​2</​mn><​mi>​n</​mi></​mrow></​msup><​mo>​=</​mo><​mn>​1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Pr _{R}[exists (x,​y):,​|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq sum _{(x,y)}Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]&​lt;​sum _{(x,​y)}2^{-2n}=1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​3c33d8d499dc7210280e9667c9e6b1a886de3780"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -3.505ex; width:​88.582ex;​ height:​6.009ex;"​ alt="​{displaystyle Pr _{R}[exists (x,​y):,​|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]leq sum _{(x,y)}Pr _{R}[|p'​_{R}(x,​y)-p(x,​y)|geq 0.1]&​lt;​sum _{(x,​y)}2^{-2n}=1}"/></​span></​dd></​dl><​p>​Bất đẳng thức cuối cùng ở trên là đúng vì có <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle 2^{2n}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msup><​mn>​2</​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​2</​mn><​mi>​n</​mi></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle 2^{2n}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​85543d7c2b7e0fea744a50af20d0f58b0f0fcfb3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​3.203ex;​ height:​2.676ex;"​ alt="​{displaystyle 2^{2n}}"/></​span>​ bộ dữ liệu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>​ khác nhau. Vì xác suất nhỏ hơn 1, nên tồn tại <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle R_{0}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​R</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​0</​mn></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle R_{0}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​9b8916196f182fcbaaca54f931176a4a4f5769cc"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​2.818ex;​ height:​2.509ex;"​ alt="​{displaystyle R_{0}}"/></​span>​ sao cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,​y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (x,​y)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​41cf50e4a314ca8e2c30964baa8d26e5be7a9386"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.328ex;​ height:​2.843ex;"​ alt="​{displaystyle (x,​y)}"/></​span>:​
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle |p'​_{R_{0}}(x,​y)-p(x,​y)|&​lt;​0.1}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​msubsup><​mi>​p</​mi><​mrow class="​MJX-TeXAtom-ORD"><​msub><​mi>​R</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​0</​mn></​mrow></​msub></​mrow><​mo>​′</​mo></​msubsup><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mo>​−<​!-- &minus; --></​mo><​mi>​p</​mi><​mo stretchy="​false">​(</​mo><​mi>​x</​mi><​mo>,</​mo><​mi>​y</​mi><​mo stretchy="​false">​)</​mo><​mrow class="​MJX-TeXAtom-ORD"><​mo stretchy="​false">​|</​mo></​mrow><​mo>&​lt;</​mo><​mn>​0.1</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle |p'​_{R_{0}}(x,​y)-p(x,​y)|&​lt;​0.1}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b2f5d39f29980cf6c80991a05b9a8c902d0a0afa"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.338ex; width:​25.511ex;​ height:​3.343ex;"​ alt="​{displaystyle |p'​_{R_{0}}(x,​y)-p(x,​y)|&​lt;​0.1}"/></​span></​dd></​dl><​p>​Vì <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle P}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​P</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle P}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b4dc73bf40314945ff376bd363916a738548d40a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.745ex;​ height:​2.176ex;"​ alt="​P"/></​span>​ có xác suất sai 0.1, nên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle P'​_{R_{0}}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msubsup><​mi>​P</​mi><​mrow class="​MJX-TeXAtom-ORD"><​msub><​mi>​R</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​0</​mn></​mrow></​msub></​mrow><​mo>​′</​mo></​msubsup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle P'​_{R_{0}}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​1363bc1c558743e3a692e8eb06927d67da22bf7e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.338ex; width:​3.803ex;​ height:​3.176ex;"​ alt="​{displaystyle P'​_{R_{0}}}"/></​span>​ có xác suất sai không quá 0.2.
 +</p>
 +<​h2><​span id="​.C4.90.E1.BB.99_ph.E1.BB.A9c_t.E1.BA.A1p_truy.E1.BB.81n_th.C3.B4ng_l.C6.B0.E1.BB.A3ng_t.E1.BB.AD"/><​span class="​mw-headline"​ id="​Độ_phức_tạp_truyền_thông_lượng_tử">​Độ phức tạp truyền thông lượng tử</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=6"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Độ phức tạp truyền thông lượng tử”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=6"​ title="​Sửa đổi phần “Độ phức tạp truyền thông lượng tử”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​Độ 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.
 +</​p><​p>​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.
 +</p>
 +<​h2><​span id="​.C4.90.E1.BB.99_ph.E1.BB.A9c_t.E1.BA.A1p_truy.E1.BB.81n_th.C3.B4ng_kh.C3.B4ng_.C4.91.C6.A1n_.C4.91.E1.BB.8Bnh"/><​span class="​mw-headline"​ id="​Độ_phức_tạp_truyền_thông_không_đơn_định">​Độ phức tạp truyền thông không đơn định</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​veaction=edit&​amp;​section=7"​ class="​mw-editsection-visualeditor"​ title="​Sửa đổi phần “Độ phức tạp truyền thông không đơn định”">​sửa</​a><​span class="​mw-editsection-divider">​ | </​span><​a href="​http://​vi.wikipedia.org/​w/​index.php?​title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng&​amp;​action=edit&​amp;​section=7"​ title="​Sửa đổi phần “Độ phức tạp truyền thông không đơn định”">​sửa mã nguồn</​a><​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​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 <​i>​f(x,​y)</​i>​. Độ 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ị <​i>​(x,​y)</​i>​ 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.
 +</​p><​p>​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 <sup id="​cite_ref-Kushilevitz_1997_2-1"​ class="​reference">​[2]</​sup><​sup id="​cite_ref-dhs96_3-0"​ class="​reference"><​a href="#​cite_note-dhs96-3">​[3]</​a></​sup>​. Độ 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.
 +</​p><​p>​Độ 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 <sup id="​cite_ref-dhs96_3-1"​ class="​reference"><​a href="#​cite_note-dhs96-3">​[3]</​a></​sup>​. Đồ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 <a href="​http://​vi.wikipedia.org/​w/​index.php?​title=H%E1%BA%A1ng_kh%C3%B4ng_%C3%A2m_(%C4%91%E1%BA%A1i_s%E1%BB%91_tuy%E1%BA%BFn_t%C3%ADnh)&​amp;​action=edit&​amp;​redlink=1"​ class="​new"​ title="​Hạng không âm (đại số tuyến tính) (trang chưa được viết)">​hạng không âm</​a>​ của một ma trận không âm.<sup id="​cite_ref-4"​ class="​reference"><​a href="#​cite_note-4">​[4]</​a></​sup></​p>​
 +
 +
 +
 +<​ul><​li><​span id="​CITEREFKushilevitzNisan1997"​ class="​citation">​Kushilevitz,​ E.; <a href="​http://​vi.wikipedia.org/​w/​index.php?​title=Noam_Nisan&​amp;​action=edit&​amp;​redlink=1"​ class="​new"​ title="​Noam Nisan (trang chưa được viết)">​Nisan,​ N.</​a>​ (1997), <​i>​Communication complexity</​i>,​ Cambridge University Press</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3A%C4%90%E1%BB%99+ph%E1%BB%A9c+t%E1%BA%A1p+truy%E1%BB%81n+th%C3%B4ng&​amp;​rft.au=Kushilevitz%2C+E.&​amp;​rft.au=Nisan%2C+N.&​amp;​rft.aufirst=E.&​amp;​rft.aulast=Kushilevitz&​amp;​rft.btitle=Communication+complexity&​amp;​rft.date=1997&​amp;​rft.genre=book&​amp;​rft.pub=Cambridge+University+Press&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li>​Brassard,​ G. Quantum communication complexity: a survey. <a rel="​nofollow"​ class="​external text" href="​http://​arxiv.org/​abs/​quant-ph/​0101005">​http://​arxiv.org/​abs/​quant-ph/​0101005</​a></​li>​
 +<​li><​span id="​CITEREFDietzfelbingerHromkovičSchnitger1996"​ class="​citation">​Dietzfelbinger,​ M.; Hromkovič, J.; Schnitger, G. (1996), “A comparison of two lower-bound methods for communication complexity”,​ <​i>​Theoret. Comput. Sci.</​i>​ <​b>​168</​b>​ (1): 39–51</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3A%C4%90%E1%BB%99+ph%E1%BB%A9c+t%E1%BA%A1p+truy%E1%BB%81n+th%C3%B4ng&​amp;​rft.atitle=A+comparison+of+two+lower-bound+methods+for+communication+complexity&​amp;​rft.au=Dietzfelbinger%2C+M.&​amp;​rft.au=Hromkovi%C4%8D%2C+J.&​amp;​rft.au=Schnitger%2C+G.&​amp;​rft.aufirst=M.&​amp;​rft.aulast=Dietzfelbinger&​amp;​rft.date=1996&​amp;​rft.genre=article&​amp;​rft.issue=1&​amp;​rft.jtitle=Theoret.+Comput.+Sci.&​amp;​rft.pages=39-51&​amp;​rft.volume=168&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span id="​CITEREFRaz2004"​ class="​citation"><​a href="​http://​vi.wikipedia.org/​wiki/​Ran_Raz"​ title="​Ran Raz">​Raz,​ Ran</​a>​ (2004), “Circuit and Communication Complexity”, ​ trong Rudich, Steven; Wigderson, Avi, <​i>​Computational Complexity Theory</​i>,​ American Mathematical Society Institute for Advanced Study, tr. 129–137</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3A%C4%90%E1%BB%99+ph%E1%BB%A9c+t%E1%BA%A1p+truy%E1%BB%81n+th%C3%B4ng&​amp;​rft.atitle=Circuit+and+Communication+Complexity&​amp;​rft.au=Raz%2C+Ran&​amp;​rft.aufirst=Ran&​amp;​rft.aulast=Raz&​amp;​rft.btitle=Computational+Complexity+Theory&​amp;​rft.date=2004&​amp;​rft.genre=bookitem&​amp;​rft.pages=129-137&​amp;​rft.pub=American+Mathematical+Society+Institute+for+Advanced+Study&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span id="​CITEREFYao1979"​ class="​citation">​Yao,​ A. C. (1979), “Some Complexity Questions Related to Distributed Computing”,​ <​i>​Proc. of 11th STOC</​i>,​ tr. 209–213</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3A%C4%90%E1%BB%99+ph%E1%BB%A9c+t%E1%BA%A1p+truy%E1%BB%81n+th%C3%B4ng&​amp;​rft.atitle=Some+Complexity+Questions+Related+to+Distributed+Computing&​amp;​rft.au=Yao%2C+A.+C.&​amp;​rft.aufirst=A.+C.&​amp;​rft.aulast=Yao&​amp;​rft.btitle=Proc.+of+11th+STOC&​amp;​rft.date=1979&​amp;​rft.genre=bookitem&​amp;​rft.pages=209-213&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span id="​CITEREFNewman1991"​ class="​citation">​Newman,​ I. (1991), “Private vs. Common Random Bits in Communication Complexity”,​ <​i>​Information Processing Letters</​i>​ <​b>​39</​b>:​ 67–71</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3A%C4%90%E1%BB%99+ph%E1%BB%A9c+t%E1%BA%A1p+truy%E1%BB%81n+th%C3%B4ng&​amp;​rft.atitle=Private+vs.+Common+Random+Bits+in+Communication+Complexity&​amp;​rft.au=Newman%2C+I.&​amp;​rft.aufirst=I.&​amp;​rft.aulast=Newman&​amp;​rft.date=1991&​amp;​rft.genre=article&​amp;​rft.jtitle=Information+Processing+Letters&​amp;​rft.pages=67-71&​amp;​rft.volume=39&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li></​ul>​
 +<​!-- ​
 +NewPP limit report
 +Parsed by mw1257
 +Cached time: 20181013012135
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.204 seconds
 +Real time usage: 0.418 seconds
 +Preprocessor visited node count: 1051/​1000000
 +Preprocessor generated node count: 0/1500000
 +Post&#​8208;​expand include size: 14792/​2097152 bytes
 +Template argument size: 137/2097152 bytes
 +Highest expansion depth: 8/40
 +Expensive parser function count: 0/500
 +Unstrip recursion depth: 0/20
 +Unstrip post&#​8208;​expand size: 7046/​5000000 bytes
 +Number of Wikibase entities loaded: 0/400
 +Lua time usage: 0.028/​10.000 seconds
 +Lua memory usage: 2.47 MB/50 MB
 +--><​!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​  ​76.641 ​     1 -total
 + ​63.18% ​  ​48.425 ​     6 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch
 + ​63.04% ​  ​48.314 ​     1 B&#​7843;​n_m&#​7851;​u:​Tham_kh&#​7843;​o
 +  5.66%    4.336      1 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_t&#​7841;​p_ch&​iacute;​
 +  4.18%    3.206      2 B&#​7843;​n_m&#​7851;​u:​Harvnb
 +  2.20%    1.684      2 B&#​7843;​n_m&#​7851;​u:​Math
 +--><​!-- Saved in parser cache with key viwiki:​pcache:​idhash:​1244095-0!canonical!math=5 and timestamp 20181013012135 and revision id 26352944
 + ​--></​div>​
 +
 +</​HTML>​
31--ph-c-t-p-truy-n-th-ng-la-gi.txt · Last modified: 2018/11/07 17:11 (external edit)