로그 순위 추측

이론 컴퓨터 과학에서 로그 순위 추측에 따르면, 양 당사자 부울 함수의 결정론적 통신 복잡성은 입력 행렬의 순위 로그와 다항적으로 관련이 있다.^[1][2]

$Let{\displaystyle }$ D${\displaystyle }$(${\displaystyle f}$) ${\displaystyle D(f)}$은 함수의 결정론적 통신 복잡성을 나타내고$$, ${\displaystyle (f}$) ${\displaystyle \operatorname {rank}(f)$은 입력 매트릭스 M ${\displaystyle f_{}}$ ${\$reals)의 순위를 나타내도록$$ 한다.최대 $c{\displaystyle }${\$displaystyle c$}비트$$ $파티션{\displaystyle {}_{}}$ ${\displaystyle M_{}}$ f$${\$displaystyle M_{f}}$을(를) 최대 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle c^{}}$ ${\$ 단색$$ 직사각형으로 사용하는$$ 모든 프로토콜이 최대 1의 순위를 가지므로,

${\displaystyle D(f)\geq \log _{2}\operatorname {rank}(f).}$

로그 순위 추측에 따르면 $D{\displaystyle (f}$) ${\displaystyle D(f)}$은(는) 로그 순위의 다항식(일부 상수 $C{\displaystyle }$ ${\displaystyle C}$에 대해서도 상한으로 되어 있다$$$.$

${\displaystyle D(f)=O(\log \operatorname {rank}(f)^{C}).}$

러브트 때문에 가장 잘 알려진 상한선은 다음과 같이 말한다.^[3]

$[\디스플레이 스타일 D(displaystyle D(f)=]O\왼쪽({\sqrt {\operatorname {rank}(f)}}}\log \operatorname {rank}(f)\오른쪽).}$

괴스, 피타시, 왓슨으로 인해 가장 잘 알려진 하한은 ^[4]${\displaystyle \mathrm{C}}$ ${\displaystyle \ge }$ 2 ${\displaystyle C\geq 2}$라고 기술하고 있다$.$ 다시 말해 로그 순위가 무한대로 가는 ${\displaystyle {함수}_{}}$ $f{\displaystyle {}_{}}$ ${\$가 있다$.$

${\displaystyle D(f_{n})={\tilde {\Oomega}}}}(\log \operatorname {rank}(f_{n})^{2}).}$

최근 그 추측의 대략적인 버전이 반증되었다.^[5]

참조