다중 통신 복잡성

이론 컴퓨터 과학에서 다중 통신 복잡성은 2명 이상의 플레이어가 있는 환경에서 통신 복잡성을 연구하는 학문이다.

야오(1979년)가 도입한 전통적 양당 커뮤니케이션 게임에서 P와₁₂ P의 두 플레이어가 부울함수를 계산하려고 시도한다.^[1]

${\displaystyle f(x_{1},x_{2}):\{0,1\}^{n}\{0,1\}\x_{1},x_{2}\in \{0,1\}^{n'},\ 2n'=n}$

플레이어 P는₁ x의₂ 값을 알고, P는₂ x의₁ 값을 알고 있지만, i_i = 1, 2에 대해서는 x의_i 값을 모른다.

선수들이 상대 변수를 알기는 하지만 자기 변수를 알지는 못한다는 얘기다.플레이어가 f를 계산하기 위해 통신해야 하는 최소 비트 수는 κ(f)로 표시된 f의 통신 복잡성이다.

1983년에 정의한 멀티파티 커뮤니케이션 게임은 양 당사자 사례의 강력한 일반화다.^[2]여기서 선수들은 자신의 의견을 제외한 다른 사람들의 의견을 모두 알고 있다.이러한 특성 때문에, 때때로 이 모델을 "이마의 숫자" 모델이라고 부르기도 하는데, 왜냐하면 선수들이 둥근 테이블에 둘러앉아 각각 이마에 자신의 입력을 쓰고 있다면, 모든 선수들이 자신의 입력을 제외한 다른 선수들의 입력을 볼 수 있기 때문이다.

공식 정의는 다음과 같다:$k{\displaystyle {}_{}}$ ${\displaystyle k}$ 플레이어$$: P ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{P\mathrm{}}_{}}$ ${\displaystyle {}_{}}$, .${\displaystyle }$. . ${\displaystyle P_{}}$k {\$displaystyle P_{1$},$P_{$2}, $...,P_{$k}}}} 부울 함수를 계산하려고 한다$$.

${\displaystyle f(x_{1},x_{2},\ldots,x_{n}):\{0,1\}^{n}\to \{0,1\}}}$

On set ${\displaystyle S=\{x_{1},x_{2},...,x_{n}\}}$ of variables there is a fixed partition ${\displaystyle A}$ of ${\displaystyle k}$ classes ${\displaystyle A_{1},A_{2},...,$$A_{k}}}$과$($와) 플레이어 $P{\displaystyle {}_{}}$ 1 ${\$1}은${\displaystyle (<img\; alt="A\_\{i\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/1aed3b5def921afbe6cc48aaf8f9b11c6f1c1e2d"\; style="vertical-align:\; -0.671ex;\; width:2.543ex;\; height:2.509ex;"\; papago-attr-id="28">}$는)${\displaystyle \mathrm{i}}$= ${\displaystyle 1}$, 2,${\displaystyle }$.${\displaystyle }$. k$${\$displaystyle i=1,2,...k}$에 대한 ${\$를 제외한 모든 변수를 알고 있다$.$ 플레이어는 계산력이 무제한이며, 모든 플레이어가 보는 칠판의 도움을 받아 통신한다.

목적은 $f{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$ 2${\displaystyle }$,${\displaystyle }$. .${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$2}, $...,x_{n})$를 계산하여 계산이 끝날 때 모든 플레이어가 이 값을 알 수 있도록 하는 것이다.$$The cost of the computation is the number of bits written onto the blackboard for the given input ${\displaystyle x=(x_{1},x_{2},...,x_{n})}$ and partition ${\displaystyle A=(A_{1},A_{2},...,Ax_{n})}$.멀티파티 프로토콜 비용은 집합 {0,ⁿ1} 및 주어진 $파티션{\displaystyle }$ A ${\displaystyle A}$에서 임의의 $x{\displaystyle }$ ${\displaystyle x}$에 대해 전달되는 최대 비트 수입니다$.$$파티션$ $A{\displaystyle }$ ${\displaystyle A}$에 대한 k {\$displaystyle{\displaystyle }$ k} $-party$ communication ${\displaystyle {complexity}_{}^{}}$, $C{\displaystyle {}_{}^{}}$($)$($){$A}^{($k$$)}(f$$)$는 f${\$$displaystystyle$ $f$$}$을(를) 계산하는 k ${\$$displaystystylek}$ 프로토콜의$$ 최소 비용이다$.$$f{\displaystyle }$ ${\displaystyle f}$의 k ${\displaystyle k}$ -party$$ 대칭 통신 복잡성은 다음과 같이 정의된다.

${\displaystyle C^{(k)}=\max _{A}C_{A}^{(k)}(f)}$

$여기$서 최대값은 집합 $x{\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$2${\displaystyle {}_{}}$,${\displaystyle }$. .${\displaystyle }$, $x n$)의 모든 k-temp에 $대해$ 취해진다$.$

상한 및 하한

일반적인 위 2더 많은 선수들 모두에게 향하는 동안 우리 조직은 A1하나를 칸막이의 가장 작은 수업 A1,A2,...,Ak의 가정해 봅시다.그리고 P1A1+:P2는 칠판에 A1의 A1비트 S의 어떤 부울 함수의 의사 소통 1인 비트를 계산할 수 있다면, P1, 및을 계산하고 값이 f발표()){f\displaystyle 그것을 읽고$(x)}}$. 따라서 다음과 같이 쓸 수 있다.

${\displaystyle C^{{(k)}\leq {\bigg \llloor }{n \over k}{\bigg \rfloor }+1.}$

GIP(^[3]Generalized Inner Product) 함수는 다음과 같이 정의된다.Let ${\displaystyle y_{1},y_{2},...,y_{k}}$ be ${\displaystyle n}$-bit vectors, and let ${\displaystyle Y}$ be the ${\displaystyle n}$ times ${\displaystyle k}$ matrix, with ${\displaystyle k}$ columns as the ${\displaystyle y$$_{1},y_{2},...,y_{k}$ 벡터$$.그런 다음 $G{\displaystyle }$ ${\displaystyle I}$ ${\displaystyle P({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$y ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. . . ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$) ${\displaystyle GIP(y_{1},y_{$2}, $...,y_{k}}}$는 모듈로$$2를 취합한 $행렬{\displaystyle }$ Y$${\$displaystyle$ Y$}$의 전체 1행 수입니다.즉, $벡터{\displaystyle {}_{}}$ ${\displaystyle {y\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{y\mathrm{}}_{}}$2${\displaystyle }$, .${\displaystyle }$. . y ${\displaystyle k_{}}$ ${\$}, $...,y_{k}}}$가 n ${\displaystyle n}$ 요소의$$ k ${\displaystyle$ k} 부분$$$집합$의 특성 벡터에$$ 해당하면 GIP는$$ 이러한 k ${\displaystyle$ k$}$ 부분 집합의$$ 교차점들의 패리티에 해당된다.

라고 보여졌다^[3].

${\displaystyle C^{{(k)}(GIP)\geq c{n \n \n \over 4^{k}},}$

상수 c > 0으로

GIP의 다중 통신 복잡성에 대한 상한은 다음을 나타낸다^[4].

${\displaystyle C^{{(k)}(GIP)\leq c{n \n \over 2^{k}},}$

상수 c > 0으로

일반 부울함수 f의 경우 다음과₁ 같은 L 규범을^[5] 사용하여 f의 다중 통신 복잡성을 막을 수 있다.^[6]

${\displaystyle C^{(k)}}(f)=O{\Bigg (}k^{2}\log(nL_{1}(f){nL_{1}^{2}(f){2^{k}}}}{\Bigg \rceil }}}}}}}}}}}}}}}}}}}}{{{{{{{{{{{{{{{{{{\Bigg}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

다중 통신 복잡성 및 유사 생성기

가성수 생성기는 GIP 함수에 대한 BNS 하한을 기반으로 했다.^[3]