通信複雑性
行列の階数は、そのサイズに対する多項式時間で計算可能であるため、通信複雑性の上限は多項式時間で計算可能と考えられる。ただし、行列のサイズは入力文字列の長さに対して指数的に増加する。
乱択プロトコルでは、やり取りするビット数の最悪ケース R(f) は以下の式に多項式的に関連すると推測される。
min ( rank ( M f ′ ) : M f ′ ∈ R 2 n × 2 n , ( M f − M f ′ ) ∞ ≤ 1 / 3 ) {\displaystyle \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3)} .
このような対数階数予想は、行列の通信複雑性の問題を行列の線形独立な行(または列)の問題に帰着させるという点で有意義である。これは通信複雑性問題の本質を明らかにする。例えば、上述の EQ の場合でもそうだが、入力が等しいかどうかを判定するために、入力が行列のどの要素に対応するかを解明する問題に帰着させていたのであった。