통신 복잡성

이론 컴퓨터 과학에서, 의사소통의 복잡성은 문제에 대한 투입물이 두 개 이상의 당사자 사이에 분배되었을 때 문제를 해결하는 데 필요한 의사소통의 양을 연구한다. 통신의 복잡성에 대한 연구는 여러 기계들 사이에 분포되어 있는 연산 문제를 연구하던 1979년 앤드루 야오에 의해 처음 도입되었다.^[1] $문제$는 보통 다음과 같이 명시된다$:$ 두 당사자(전통적으로 $앨리스$와 밥이라고 함)는 각각 ($잠재적$으로 $다른$$)$ n을 $받는다{\displaystyle }$$.$ 목표는 앨리스가 그들 사이의 최소한의 통신량을 가지고 $x{\displaystyle }$ ${\displaystyle$ x$\}$과 y ${\displaystyle$ $y$$}$둘 다에 의존하는 $f{\displaystyle }$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle f(x,y$의 값을 계산하는 것이다.

앨리스와 밥은 밥에게 그의 전체 $n{\displaystyle }$ ${\displaystyle$ $n$$}$ -bit$$ 문자열을 앨리스($그{\displaystyle }$ 다음 함수 f ${\displaystyle$ f$})$에게 보내도록 함으로써 항상 성공할 수 있지만,$$ 여기서의 $생각$은 n ${\displaystyle n}$비트$$ 이하의 $통신$으로 f ${\displaystyty$ f$}$를 계산하는 교묘한 방법을 찾는 것이다. 컴퓨터 복잡성 이론에서와 달리, 통신 복잡성은 앨리스나 밥이 수행하는 계산량이나, 우리가 일반적으로 앨리스나 밥의 계산 능력에 대해 아무 것도 가정하지 않기 때문에, 사용되는 메모리의 크기와는 상관이 없다는 점에 유의한다.

두 당사자의 추상적인 문제(양자간 의사소통 복잡성이라고 불림), 그리고 두 당사자가 넘는 그것의 일반적인 형태는 여러 맥락에서 관련된다. 예를 들어, VLSI 회로 설계에서는 분산 계산 중에 서로 다른 구성 요소 간에 전달되는 전기 신호의 양을 줄임으로써 사용되는 에너지를 최소화하려고 한다. 이 문제는 데이터 구조의 연구와 컴퓨터 네트워크의 최적화에도 관련이 있다. 현장 조사는 쿠실레비츠&니산(2006)의 교재를 참조한다.

형식 정의

Let ${\displaystyle f:X\times Y\rightarrow Z}$ where we assume in the typical case that ${\displaystyle X=Y=\{0,1\}^{n}}$ and ${\displaystyle Z=\{0,1\}}$. Alice holds an ${\displaystyle n}$-bit string ${\displaystyle x\in X}$ while Bob holds an ${\disp$$레이스타일 n}$ -bit$$ 문자열 y$$ ${\displaystyle Y}$ {\$displaystyle y\in$ Y$\}.$ 한 번에 한 비트씩 서로 통신함으로써(사전 합의된 일부 통신 프로토콜을 채택함) 앨리스와 밥은 적어도 한 당사자가 통신의 끝에서 값을 알 수 $있도록$ f${\displaystyle (x}$,${\displaystyle y}$ $){\displaystystyle f(x,y)}$의 값을 계산하고자 한다. 이 시점에서 답은 다시 전달되어 1비트의 추가 비용이 들더라도 양 당사자가 답을 알 수 있도록 할 수 있다. $D{\displaystyle }$( ${\displaystyle f}$) ${\displaystyle D(f)}$로 표시된$$컴퓨팅 $f{\displaystyle }$ ${\displaystyle f}$의 이 통신 문제의 최악의 경우 통신 복잡성은 다음으로 정의된다$.$

${\displaystyle D}$( ${\displaystyle f}$)${\displaystyle }$= ${\displaystyle D(f)=}$ 최악의 경우 앨리스와 밥 사이에 교환된 최소$$ 비트 수.

As observed above, for any function ${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$, we have ${\displaystyle D(f)\leq n}$. Using the above definition, it is useful to think of the function ${\displaystyle f}$ as a matrix ${\displaystyle A}$$$ (called the input matrix or communication matrix) where the rows are indexed by ${\displaystyle x\in X}$ and columns by ${\displaystyle y\in Y}$. The entries of the matrix are ${\displaystyle A_{x,y}=f(x,y)}$. Initially both Alice and Bob have a copy of the entire matrix ${\displaysty$$le$ A$}($$f{\displaystyle }$ ${\displaystyle f}$ 함수를 가정하면 양 당사자에게 알려져 있다$$). 그런 다음 함수 값의 계산 문제는 해당 매트릭스 엔트리에서 "제로잉인"으로 다시 번역할 수 있다. 이 문제는 앨리스나 밥이 $x{\displaystyle }$ ${\displaystyle$ x$}$와 $y{\displaystyle }$ ${\displaystyle y}$을(를) 모두 알면 해결될 수 있다$.$ 통신 시작 시 입력에 있는 함수의 값에 대한 선택 횟수는 매트릭스 크기, 즉 ${\displaystyle {\mathrm{2n}}^{}}$ ${\$ 2$^{2n$ 그리고 나서 각 당사자가 상대방에게 약간씩 통신할 때와 같이 해결된다.이렇게 하면 $A{\displaystyle }$ ${\displaystyle A}$의 하위 계층이 생성되는 일련의 행/색상이 제거됨에 따라 답변 선택 횟수가 감소한다$.$

More formally, a set ${\displaystyle R\subseteq X\times Y}$ is called a (combinatorial) rectangle if whenever ${\displaystyle (x_{1},y_{1})\in R}$ and ${\displaystyle (x_{2},y_{2})\in R}$ then ${\displaystyle (x_{1},y_{2})\in R}$. Equivalently, ${\displaystyle R}$ is a combinatorial rectangle if it can be expressed as ${\displaystyle R=M\times N}$ for some ${\displaystyle M\subseteq X}$ and ${\displaystyle N\subseteq Y}$. Consider the case when ${\displaystyle k}$ bits are already exchanged between the parties. 이제 특정 $h{\displaystyle \in \{0}$, ${\displaystyle 1}$ ${\displaystyle {}^{}}$ k ${\$에 대해 행렬을 정의해 봅시다$.$

${\displaystyle T_{h}=\{(x,y):{\text{{}k{{}k{\text{-bits 교환은 입력 }}(x,y){\text{}는 }h\}}이다.$

그렇다면 T ${\displaystyle h_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle X}$ ${\displaystyle \times }$ ${\displaystyle Y}$ ${\displaystyle T_{h}\subseteq X\time Y$ $그리고{\displaystyle {}_{}}$ T$$h {\$displaystyle T_{$h}}는 $A{\displaystyle }$ ${\displaystyle$ A$}$의 $조합형$ 직사각형임을 보여주는 것은 어렵지$$ 않다$.$

예: ${\displaystyle E}$ $Q{\displaystyle }$ ${\displaystyle EQ}$

우리는 앨리스와 밥이 그들의 입력 문자열이 동일한지 여부를 결정하려고 하는 경우를 고려한다. Formally, define the Equality function, denoted ${\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$, by ${\displaystyle EQ(x,y)=1}$ if ${\displaystyle x=y}$. As we demonstrate below, any deterministic communication protocol solving $$${\displaystyle E}$ ${\displaystyle Q}$ ${\displaystyle$ EQ$}$에는 최악의 경우 $n{\displaystyle }$ ${\displaystyle$ n}비트의$$ 통신이$$ 필요하다. 예열 예로서 ${\displaystyle x}$, y ${\displaystyle \in }${ 0${\displaystyle ,}$ ${\displaystyle {1\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ 3 ${\$의 간단한 경우를 생각해 보십시오$.$ 이 경우 동등함수는 아래 행렬로 나타낼 수 있다. 행은 $x{\displaystyle }$ ${\displaystyle x}$의 모든 가능성$,$ $y{\displaystyle }$ ${\displaystyle y}$의 열을 나타낸다$.$

EQ	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

보시다시피 함수는 $x{\displaystyle }$ ${\displaystyle x}$이(가) $y{\displaystyle }$ ${\displaystyle y}($즉, 대각선)일$$ 때만 1로 평가된다. 또한 의사소통 한 부분이 어떻게 당신의 가능성을 반으로 나누는지 보는 것은 꽤 쉽다. $y{\displaystyle }$ ${\displaystyle y}$의 첫 번째 비트가 1인$$ 것을 알고 있으면 열의 절반만 고려하면 된다(y ${\displaystyle y}$이($가{\displaystyle }$) 100, 101, 110 또는 111일 수 있음$$).

정리: $D{\displaystyle }$( ${\displaystyle E}$ ${\displaystyle Q}$)${\displaystyle }$= ${\displaystyle n}$ ${\디스플레이$ 스타일 $D(EQ)=n}$

Proof. Assume that ${\displaystyle D(EQ)\leq n-1}$. This means that there exists ${\displaystyle x\neq x'}$ such that ${\displaystyle (x,x)}$ and ${\displaystyle (x',x')}$ that have the same communication transcript ${\displaystyle h}$. Since this transcript d직사각형, $f{\displaystyle ({}^{}}$, x ${\displaystyle {\prime }^{}}$) ${\displaystyle f(x,x')}$도 1이어야 한다$$. $정의상{\displaystyle }$ x${\displaystyle }$′ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$에 따라 $a{\displaystyle }$= b ${\displaystyle a=b}$일 때$,{\displaystyle }$ ${\displaystyle \mathrm{우리}}$는${\displaystyle (,}$ b$$) {\$displaystyle (a,$b)}에 대해서만 동등하다는 것을 알고 있다$.$ 이것은 모순을 낳는다.

결정론적 의사소통 하한을 증명하는 이 기법을 바보 세트 기법이라고 한다.^[2]

무작위화된 통신 복잡성

위의 정의에서 우리는 두 당사자 간에 결정적으로 전송되어야 하는 비트 수에 대해 염려한다. 양 당사자에게 무작위 번호 생성기에 대한 액세스 권한이 부여된 경우 $교환$되는 정보가 훨씬 적은$$ f ${\displaystyle f}$의 값을 결정할 수 있는가? 야오밍은 그의 논문에서^[1] 무작위화된 의사소통의 복잡성을 정의함으로써 이 질문에 대답한다.

$함수{\displaystyle }$ f ${\displaystyle f}$에 대한 임의화된 $프로토콜{\displaystyle }$ R ${\displaystyle R}$에는 양면 오류가 있다$$.

${\displaystyle \Pr[R(x,y)=0]}{\frac {2}{3},{\textrm {if}\,f(x,y)=0}$

${\displaystyle \Pr[R(x,y)=1]{\frac {2}{3},{\textrm {if}\,f(x,y)=1}$

무작위화 프로토콜은 정규 입력 외에 추가 랜덤 문자열을 사용하는 결정론적 프로토콜이다. 이를 위한 두 가지 모델이 있는데, 공용 문자열은 양 당사자가 사전에 알고 있는 임의 문자열이며, 개인 문자열은 한 당사자가 생성하여 상대방에게 전달해야 한다. 아래에 제시된 정리는 모든 공개 문자열 프로토콜이 원본과 비교하여 O(log n) 추가 비트를 사용하는 사설 문자열 프로토콜에 의해 시뮬레이션될 수 있음을 보여준다.

위의 확률 불평등에서 프로토콜의 결과는 무작위 문자열에만 의존하는 것으로 이해되며, x와 y 문자열 모두 고정된 상태로 유지된다는 점에 유의하십시오. 즉, 무작위 문자열 r을 사용할 때 R(x,y,y)이 g(x,y,r)를 산출하면 g(x,y,r) = f(x,y)가 문자열 r에 대한 모든 선택사항의 최소 2/3에 대해 산출한다.

무작위화된 복잡성은 단순히 그러한 프로토콜에서 교환되는 비트 수로 정의된다.

단측 오류로 무작위화된 프로토콜을 정의할 수도 있으며, 복잡성은 유사하게 정의된다.

예: EQ

EQ의 이전 예로 돌아가서 확실성이 필요하지 않은 경우 앨리스와 밥은 $O{\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle$ O$(\log n)}$ 메시지만$$ 사용하여 동등성을 확인할 수 있다. 다음 프로토콜을 고려하십시오. Assume that Alice and Bob both have access to the same random string ${\displaystyle z\in \{0,1\}^{n}}$. Alice computes ${\displaystyle z\cdot x}$ and sends this bit (call it b) to Bob. (The ${\displaystyle (\cdot )}$ is the dot product in GF(2).) 그리고 나서 밥은 b를 $z{\displaystyle }$ ${\displaystyle \cdot }$ ${\displaystyle y}$에 비교한다$.$$$만약 $그것들$이 같다면, 밥은 x와 y가 $같다고 말하면서$ 받아들인다. 그렇지 않으면 그는 거절한다.

Clearly, if ${\displaystyle x=y}$, then ${\displaystyle z\cdot x=z\cdot y}$, so ${\displaystyle Prob_{z}[Accept]=1}$. If x does not equal y, it is still possible that ${\displaystyle z\cdot x=z\cdot y}$, which would give Bob the wrong answer. 어떻게 이런 일이 일어날까?

x와 y가 같지 않은 경우, 일부 위치에서는 달라야 한다.

${\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}$

${\displaystyle x_{}}$와 y가 일치하는 경우, $z{\displaystyle {}_{}}$ i ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle z_{}}$ ${\displaystyle {}_{}{}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ i${\displaystyle {}_{}{y}_{}}$ y i$${\$displaystyle z_{i}**x_{i}=z_{i$}*$c_{i}=z_${i$}y_{i}}}}}}}},$ 따라서 이러한 용어는 도트 제품에 동등하게 영향을$$ 미친다. 우리는 그러한 용어들을 안전하게 무시하고 x와 y가 다른 부분만 볼 수 있다. 게다가 우리는 ${\displaystyle {도트}_{}}$ 제품의 동일 여부를 변경하지 않고$$ x $i{\displaystyle {}_{}}$ ${\$와 ${\displaystyle y_{}}$ i ${\$를 교환할 수 있다. 즉, x에 0만 포함되고 y에 0만 포함되도록 비트를 교환할 수 있다.

${\displaystyle {\case}x'=00\ldots 0\y'=11\dots 1\\z'=z_{1}z_{1}z_{1}dots z_{n'}\end{case}}}}}}}}}$

Note that ${\displaystyle z'\cdot x'=0}$ and ${\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}$. Now, the question becomes: for some random string ${\displaystyle z'}$, what is the probability that ${\displaystyle \Sigma _{i}z'_{i}=0}$? Since each $$${\displaystyle z'_{i}}$ is equally likely to be 0 or 1, this probability is just ${\displaystyle 1/2}$. Thus, when x does not equal y, ${\displaystyle Prob_{z}[Accept]=1/2}$. The algorithm can be repeated many times to increase its accuracy. 이것은 무작위화된 통신 알고리즘에 대한 요건에 적합하다.

This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute ${\displaystyle EQ(x,y)}$. In the next section, it is shown that Alice and Bob can exchange only ${\displaystyle O(\log n)}$ bits that are as good as sharing a random string of length n. 일단 그것이 표시되면, $EQ$는 O${\displaystyle }$( ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle n}$) ${\displaystyle O(\log$ n$)}$ 메시지로$$ 계산될 수 있다.

예:GH

그러나 무작위화된 통신 복잡성의 또 다른 예에 대해서는 갭 해밍 문제(약칭 GH)로 알려진 예를 들 수 있다. 공식적으로 앨리스와 밥은 둘 다 $이진{\displaystyle }$ 메시지 x${\displaystyle }$, ${\displaystyle y}$ ${\displaystyle \in }${${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle }$+ 1${\displaystyle {}^{}\mathrm{n}}$ ${\$ x$,y\in \{-1,+1\}^{n}}$을 유지하며$$ 문자열이 매우 유사한지 또는 매우 유사한지 여부를 확인하고자 한다. 특히 다음과 같은 부분 부울 함수를 계산하기 위해 가능한 한 적은 수의 비트의 전송을 요구하는 통신 프로토콜을 찾고자 한다.

${\displaystyle {\text{GH}_{n}(x,y):={\cHB{case}-1&\langle x,y\langle \leq -{\sqrt{n}\\n1}\langle x,y\langle \geq {\sqrt {n}.\end{case}}}$

분명히, 프로토콜이 결정론적이라면, 그들은 모든 비트를 전달해야 한다(이것은 앨리스와 밥이 서로 중계하는 결정론적이고 엄격한 지수의 부분 집합이 있다면, 그 집합에서 ${\displaystyle \mathrm{n}}$- 1 ${\displaystyle {\sqrt{n}-1$} 위치에서$$ 일치하지 않는 한 쌍의 문자열을 상상해보라. 릴레이되지 않은 위치에서 또 다른 불일치가 발생하면 ${\displaystyle {}_{}}$ n${\displaystyle {}_{}}$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle {\text{$$GH}_{n}(x,y$ 따라서 절차가 잘못될 수 있다.

그러면 자연스럽게 질문하게 되는 것은, ${\displaystyle 1\mathrm{}}$/ 3 ${\displaystyle 1/3}$의 시간$$(임의의 인스턴스 $x{\displaystyle }$, y ${\\displaystyle$ x$,y$$\}){\displaystyle }$을(를)${\displaystyle }${${\displaystyle }$-${\displaystyle }$1, +${\displaystyle {}^1}$ n$${\$displaystyle \{-1\}^{n}}}}}$에서 무작위로 그릴$$ 수 있다면,$$ 비트가 적은 프로토콜을 사용할 수 있는가? 2012년 Chakrabarti와 Regev의 결과로 인해 다소 놀라운 대답은 no인 것으로 밝혀졌다. 즉, 임의의 경우, $적어도{\displaystyle \mathrm{}}$ 2$[\displaystyle 2/3}$ 시간의 모든$$ 절차가 $\Omega {\displaystyle \mathrm{}(n}$ ${\displaystyle )}$ ${\displaystyle \Oomega(n)}$비트$$ 가치의 통신을 전송해야 한다는 것을 보여준다. 그들.

공공화폐 대 개인화폐

쌍방이 동일한 임의 문자열(공유 문자열 프로토콜)에 접근할 수 있을 때 임의 프로토콜을 만드는 것이 더 쉽다. 두 당사자가 적은 통신비로 임의 문자열(프라이빗 스트링 프로토콜)을 공유하지 않는 경우에도 여전히 이러한 프로토콜을 사용할 수 있다. 임의의 수의 임의 문자열을 사용하는 공유 문자열 랜덤 프로토콜은 추가 O(log n) 비트를 사용하는 개인 문자열 프로토콜로 시뮬레이션할 수 있다.

직관적으로, 우리는 오차가 조금만 증가해도 랜덤 프로토콜을 실행할 수 있을 만큼 충분히 랜덤성이 있는 문자열 세트를 찾을 수 있다. 이 세트는 사전에 공유할 수 있으며, 임의의 문자열을 그리는 대신 앨리스와 밥은 공유된 집합에서 어떤 문자열을 선택할지 합의만 하면 된다. 이 세트는 선택이 효율적으로 전달될 수 있을 정도로 작다. 형식적인 증거가 뒤따른다.

최대 오류율이 0.1인 일부 임의 프로토콜 P를 고려하십시오. Let ${\displaystyle R}$ be ${\displaystyle 100n}$ strings of length n, numbered ${\displaystyle r_{1},r_{2},\dots ,r_{100n}}$. Given such an ${\displaystyle R}$, define a new protocol ${\displaystyle P'_{R}}$ which randomly picks some ${\displaystyle$$$${\displaystyle {r\_}_{}}$${i}}}$을(를) 수행한 다음 r i ${\$을(를) 공유 임의 문자열로$$ 사용하여 P를 실행하십시오. $r{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 선택 사항을 전달하려면 O(log 100n) = O(log n) 비트가 필요하다$.$

Let us define ${\displaystyle p(x,y)}$ and ${\displaystyle p'_{R}(x,y)}$ to be the probabilities that ${\displaystyle P}$ and ${\displaystyle P'_{R}}$ compute the correct value for the input ${\displaystyle (x,y)}$.

고정$({\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,y)}$에 대해서는 회프딩의 불평등을 이용하여 다음과 같은 방정식을 얻을 수 있다$.$

${\displaystyle \Pr_{R}[p'_{R}(x,y)-p(x,y) \geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}}}}{-2n}}}}}$

따라서${\displaystyle }$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,y)}$을(를) 수정하지 않은 경우:

${\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]<\sum _{(x,y)}2^{-2n}=1}$

위의 마지막 평등은 2 ${\displaystyle {\mathrm{2n}}^{}}$ ${\$ 2$^{2n}$개의$$ 다른 쌍$({\displaystyle x}$, y${\displaystyle }$) ${\displaystyle (x,$$y$$)}$이 있기 때문에 유지된다$.$ 확률은 1이 아니기 ${\displaystyle \mathrm{때문}}$에 R 0 ${\$이 일부 있으므로 ($x$ ,${\displaystyle }$y )${\displaysty$

${\displaystyle p'_{R_{0}(x,y)-p(x,y) <0.1}$

$P{\displaystyle }$ ${\displaystyle P}$은(는) 최대 0.1 오류 확률을 가지므로$$ $P{\displaystyle {}_{}^{}}$ R ${\displaystyle {{0\mathrm{}}_{}}_{}^{}}$′ ${\$은(는) 최대 0.2 오류 확률을 가질 수 있다$$.

양자 통신 복잡성

양자 통신 복잡성은 분산 연산 중 양자 효과를 이용하여 가능한 통신 감소를 정량화하려고 한다.

통신 복잡성에 대한 적어도 세 가지 양자 일반화가 제안되었다. 설문조사는 G. Brassard의 제안된 텍스트를 참조하라.

첫 번째는 qubit-communication 모델인데, 예를 들어 광섬유를 통해 광자를 교환하는 등 당사자들이 고전적 통신 대신 양자 통신을 이용할 수 있다.

두 번째 모델에서 통신은 여전히 클래식 비트로 수행되지만 당사자들은 프로토콜의 일부로 양자 얽힘 상태의 무제한 공급을 조작할 수 있다. 서로 얽혀 있는 상태를 측정함으로써, 당사자들은 분산된 계산 동안 고전적인 의사소통을 절약할 수 있다.

세 번째 모델은 쿼비트 통신 외에 이전에 공유된 얽힘에 대한 접근을 포함하며, 세 가지 양자 모델 중 가장 덜 탐구된 모델이다.

비결정적 통신 복잡성

비결정론적 의사소통의 복잡성 속에서 앨리스와 밥은 신탁에 접근할 수 있다. 오라클의 말을 받은 후, 당사자들은 $f{\displaystyle }$( x${\displaystyle }$, ${\displaystyle y}$) ${\displaystyle f(x,y)}}$을$($를) 추론하기 위해 의사소통한다$.$$$비결정론적 의사소통의 복잡성은 교환된 비트 수와 오라클 워드의 코딩 길이의 합계에 걸쳐$$ 모든 쌍$x$, $y$)에 걸쳐 최대가 된다.

다르게 보면, 이는 콤비네이터 1-제곱에 의한 0/1 매트릭스의 모든 1-제곱(즉, 비연속적, 비콘벡스 하위 연산자, 입력 내용이 모두 1이다(쿠시레비츠, 니산 또는 디츠펠빙거 외 참조). 비결정론적 통신 복잡성은 매트릭스 숫자를 포함하는 사각형의 이진 로그로, 0-엔티어를 포함하지 않고 매트릭스의 모든 1-엔티어를 포함하는데 필요한 최소 조합 1-직사각형의 수입니다.

비결정론적 의사소통 복잡성은 결정론적 의사소통 복잡성에 대한 하한을 얻기 위한 수단으로서 발생한다(Dietzfelbinger et al. 참조). 그러나 또한 비부정 행렬의 비부정 순위에 대한 하한을 부여하는 비부정 행렬 이론에서도 나타난다.^[3]

무제한 오류 통신 복잡성

무제한 오류 설정에서 앨리스와 밥은 개인 코인과 그들 자신의 입력$({\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,y)}}$에 접근할 수 있다$.$ 이 설정에서 앨리스는 1/2 이상의 확률을 $가지고{\displaystyle }$ f$$${\displaystyle (x}$ , ${\displaystyle y}$)$${\$displaystyle f(x,y)}$의 정확한 값으로 응답하면 성공한다. 즉, 앨리스의 $응답$이 f$($$x$, ${\displaystyle y}$)의$$참값과 $0$이 아닌 상관관계가 있다면,$프로토콜$은 유효한 $것$으로 간주된다$.$

코인이 비공개라는 요건은 필수적이라는 점에 유의한다. 특히 앨리스와 밥이 공유하는 공개 비트의 수가 통신의 복잡성에 반하여 계산되지 않는다면, 어떤 기능이라도 ${\displaystyle \mathrm{계산}}$하면 O${\displaystyle }$( 1${\displaystyle }$) ${\displaystyle O(1)}$의 통신 복잡성이 있다고 주장하기 쉽다.^[4] 한편, 앨리스와 밥이 사용하는 공개 비트의 수를 프로토콜의 총 통신에 반하여 계산하면 두 모델 모두 동등하다.^[5]

이 모델의 하한은 미묘하지만 매우 강하다. 좀 더 구체적으로, 이 세분류의 문제에 대한 구속은 결정론적 모델과 민간 및 공공 코인 모델의 문제에 대한 등가 한계를 즉시 암시한다는 것은 명백하지만, 그러한 한계는 비결정적 통신 모델과 양자 통신 모델의 경우에도 즉시 유지된다.^[6]

Forster[7]은 이 클래스에 대한 더 낮은 범위를 명시적, 내면의 제품 ⟨ 컴퓨팅)을 보여 주고 처음으로 증명한 것이었다, y⟩{\displaystyle\langle x,y\rangle}적어도Ω(n)을 요구한다 통신도 조금, 비록 Alon, 프랑클, Rödl의 초기 결과 증명{\displaystyle \Omega(n)}이 alm의 통신 복잡도.ost 모든 Boolean ${\displaystyle \mathrm{함수}}$f${\displaystyle }$:${\displaystyle }${ ${\displaystyle 0{}^{}}$ ${\displaystyle 1^{}}$n${\displaystyle }$×${\displaystyle }${ ${\displaystyle 0{}^{}{1}^{}\mathrm{n}}$ → {${\displaystyle 0}$, 1$}$ {\$displaystyle f:\{0,1\}^{n$}\time$\{0,1\}\\}\{0,1\}\}\}$는 $\Omega {\displaystyle \mathrm{}(n)}$이고 ${\displaystystyledown Oomega(n)$입니다$.$^[8]

문제 열기

Considering a 0 or 1 input matrix ${\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}$, the minimum number of bits exchanged to compute ${\displaystyle f}$ deterministically in the worst case, ${\displaystyle D(f)}$, is known to be bounded from below by the logarithm ${\displaystyle {매트릭스}_{}}$ M$$f {\$displaystyle M_${f$}$의 순위의 $.$ The log rank conjecture proposes that the communication complexity, ${\displaystyle D(f)}$, is bounded from above by a constant power of the logarithm of the rank of ${\displaystyle M_{f}}$. Since D(f) is bounded from above and below by polynomials of log rank${\displaystyle (M_{f})}$, we can say D(f) 다항식적으로 로그 순위${\displaystyle M_{}}$ f${\displaystyle {}_{}}$) ${\displaystyle (M_{f}})$와 관련이 있다$.$ 행렬의 순위는 행렬의 크기로 계산 가능한 다항식 시간이기 때문에, 그러한 상한은 다항식 시간에서 행렬의 통신 복잡성을 근사하게 추정할 수 있다. 그러나 행렬 자체의 크기는 입력의 크기에서 지수적이라는 점에 유의하십시오.

무작위화된 프로토콜의 경우, 최악의 경우 R(f)에서 교환되는 비트 수는 다항식으로 추측된다.

${\displaystyle \log \min({\textrm {rank})(M'_{f}):M'_{f}\in \mathb {R} ^{2^{n}\times 2^{n}, (M_{f}-M'_{f}}_{\infit }\leq 1/3)).}$

이러한 로그 순위 추정은 행렬의 통신 복잡성에 대한 질문을 행렬의 선형 독립 행(열)의 문제로 줄이기 때문에 가치가 있다. 이는 통신 복잡성 문제의 본질, 예를 들어 위의 EQ 사례에서 입력이 매트릭스 내에서 어디에 있는지 파악하여 입력이 동등한지 여부를 알아내는 데 있다는 것을 보여준다.

적용들

의사 결정 트리 복잡성, VLSI 회로, 데이터 구조, 스트리밍 알고리즘, 튜링 기계에 대한 공간-시간 트레이드오프 등의 하한을 입증하는 데 통신 복잡성의 하한을 사용할 수 있다.^[2]

참고 항목

• 갭 해밍 문제

메모들

참조

• Kushilevitz, Eyal; Nisan, Noam (2006). Communication complexity. Cambridge: Cambridge University Press. ISBN 978-0-521-02983-4. OCLC 70764786.
• Brassard, G. 양자간 의사소통의 복잡성 : 조사. https://arxiv.org/abs/quant-ph/0101005
• 디테즈펠빙거, M, J. 흐롬코비치, J, 그리고 G. 슈니터, "통신의 복잡성에 대한 두 가지 하한 방법의 비교", "이론트". 계산하다. 168, 1996, 39-51
• 라즈, 란. "회로와 통신의 복잡성" 계산 복잡성 이론에서. 스티븐 루디치와 에이비 위그더슨, 에드스 미국수학학회 2004. 129-137.
• A. C. Yao, "분산 컴퓨팅과 관련된 몇 가지 복잡성 질문", 11번째 STOC의 Proc., 페이지 209–213, 1979. 14
• I. 뉴먼, 일병 vs. 통신 복잡성의 일반 무작위 비트, 정보 처리 편지 39, 1991, 페이지 67–71.