環と半環上の行列積やその検査について

行列積についてのメモついでに.

行列積アルゴリズムは応用上重要であり, これまで様々な研究がなされてきました.
現在のところ知られている最速なアルゴリズムは, $n \times n$行列$A,B$に対して$O(n^{2.38...})$時間で積$A\cdot B$を計算できます.

一方三つの$n\times n$行列$A,B,C$が与えられたときに$A\cdot B=C$であるか否かを判定するアルゴリズムは, $O(n^2)$時間で判定する乱択アルゴリズムが知られています(実際にはモンテカルロアルゴリズムで, 高々0.5の確率で$A\cdot B\neq C$なのに$A=B$と出力してしまいます).

さて, 行列積について見るとき, ほとんどの方はそれが通常の実数$\mathbb{R}$または有理数$\mathbb{Q}$上の演算で解釈しているはずです. しかし組合せ最適化の文脈ではしばしば$(\min,+)$代数が出てきます. $(\min,+)$代数は$\mathbb{R}\cup \{\infty\}$上で定義される代数系で, 要するに$a+b:=\min(a,b)$, $a\cdot b:=a+b$(通常の実数の和)として定められます. この算数は例えばグラフの最短経路を考える際に役に立ちます. そして$(\min,+)$代数の他にも数学・情報科学ではトロピカル代数(いわゆる$(\max,+)$代数のことで, Maslov 代数などとも呼ばれます), $(\max,\min)$代数, (AND, OR)代数などが知られています. ちなみにMaslov代数は本当に面白いので余裕があればこの論文とこの論文とこの記事などをさらっと眺めて見るのも良いかもしれません. そしてこれらの代数系は半環と呼ばれるものであり, "引き算"がありません. 例えば, $(\min,+)$代数においては加法の単位元が$\infty$になるわけですが, 任意の$a\in \mathbb{R}$に対して$\min(a,x)=\infty$となる$x$は存在しません. 環では加法の逆元が存在し, 半環ではそれが存在しない. これが重要なポイントです.

さて, 先ほど紹介した環上の$O(n^2)$時間の行列積検査アルゴリズムは, $n$次元ベクトル$r$を, 各成分$r_i \in \{0,1\}$をランダムに決めて生成し, $x=A(Br)$と$y=Cr$をそれぞれ計算し, $x=y$なら$A=B$, そうでないならば$A\neq B$と出力するものです.
ここでは $\mathrm{Pr}[ABr=Cr | AB\neq C] \leq 0.5$を示せば良いのですが, $D=AB-C$とすると(今は環で考えているので引き算が使えます), ある$i,j$が存在して$D_{ij}\neq 0$となるはずです. この$i,j$に対して

$\mathrm{Pr}[Dr=0 | D\neq 0]\leq \mathrm{Pr}[(Dr)_i=0 | D_{ij}\neq 0] = \mathrm{Pr}[D_{ij}r_j = -\sum_{k\neq j}D_{ik}r_k | D_{ij}\neq 0]\leq 0.5$

が成り立つので, 上の主張が示されたことになります. しかしここでの証明では$D=AB-C$を考えていたので, 代数系としては環であることを用いてます. では引き算が使えない半環だとどうなのでしょうか？

また, 行列積を$O(n^{2.807...})$時間で計算するかの Strassenのアルゴリズムでもやはり, 解をマージする部分で引き算を使っているので, 環のためのアルゴリズムになっています.

半環であっても実際に$A\cdot B$は愚直にやれば$O(n^3)$時間で計算できるので, $O(n^3)$時間で半環上の行列積や検査ができます. 一方で行列の入力に$\Omega(n^2)$時間は最低でもかかります. では$O(n^3)$より高速に, 例えば$O(n^{2.7})$時間とかで計算できないのでしょうか？

実は, 半環はおろか$(\min, +)$代数に対しては積の計算・検査は出来ないだろうと考えられていて,  計算複雑性理論においては任意の$\epsilon>0$に対して$O(n^{3-\epsilon})$時間で$(\min,+)$代数上の行列積の計算・検査はどちらも計算出来ないと考えられています.
そして実は$(\min,+)$代数上の行列積とグラフの全点対最短経路問題は似ている構造を持った問題であり, 一方が$\tilde{O}(n^{3-\epsilon})$時間で解けたらもう一方も同様の計算時間で解けるという結果が2010年に示されました ($\tilde{O}$は$\mathrm{poly}(\log n)$を無視したオーダーの意).