はじめに
この記事は#アカンクリスマスアドベントカレンダー2023 24日目の記事です．
アドカレのネタを考えていたら，SETH で LCS の計算量の下界を示せることの証明が気になっていたことを思い出したので，それについて調べて書くことにしました．
SETH や LCS についてはのちほどきちんと説明しますが，ここでもざっくりと説明しておきます．SETH は直感的には「SAT という問題に対して変数割り当ての全探索より指数的に高速に解くアルゴリズムは存在しない」という仮定です．SAT は NP 完全な問題なので P$\neq$NP を強くした仮定とも言えるでしょう．LCS （Problem）は「2つの文字列が与えられたとき，その2つの文字列に共通する部分列（元の文字列から一部の文字を削除した文字列）のうち，最長のものを見つける」という問題です．LCS の入力として文字列 $A,B(|A|=|B|=n)$ が与えられるとき，$O(n^2)$時間で動作するアルゴリズムが知られていますが，SETH の下で任意の $\delta > 0$ に対し $O(n^{2-\delta})$ で動作するアルゴリズムが存在しないことが示せるようです(これは既知の LCS のアルゴリズムに対して漸近的な計算量の改善を行うことは SETH を否定することと同等に難しいことを示しています)．これはとても興味深い結果なので，今回はこれを示すことを目標にします．
しかし，この記事を書くにあたって，一つ課題があります．それは，SETH は Acompany に直接関係しないということです．Acompany アドベントカレンダーでは「Acompany に関係すること」を書かなければならないという制約があります．
そんなアカンメンバーが「Acompanyに関係すること」というテーマで記事を書き、毎日違ったAcompanyの多様性を披露していきますのでお楽しみに。
そこで，本記事の内容と Acompany が関係することを示さなければなりません．ここでは，暗号の安全性の話に関連づけようと思います（暗号の安全性が Acompany と関係があることは自明）．暗号の安全性には計算量的安全性というものがあり，多項式時間の攻撃者にとって分布の見分けがつかないことなどと定義されます(そのような定義が用いられているAcompany 技術ブログ記事の具体例【技術】コミットメントとゼロ知識証明 ，Oblivious Transfer〜実装と理論〜，【技術】MPC技術入門② MPCのセキュリティ定義)．このような定義の下でプロトコルの安全性を示すときには素因数分解や離散対数問題の困難性，CDH仮定などの仮定に帰着することが多いです．この証明の流れは SETH の下で計算量の下界を示すときとほぼ同じといえます．また，SETH を用いて素因数分解や離散対数問題などの問題の計算量について調べられると面白いと思うので(結局 SAT に帰着しないといけないので難しい気がしますが)，これはもう関係があると言ってよいでしょう．
SETH
SETH は CNF-SAT の計算量に対する仮定です．
したがって，まずは SAT (Satisfiability Problem:充足可能性問題)について説明します．SAT は1つの論理式が与えられたとき，その式を True にする変数の割り当てが存在する（充足する）かを判定する問題です．SAT の中でも，論理式が節の論理積からなるものを CNF-SAT といいます．各節に現れる変数が高々 $k$ 個である CNF-SAT を $k$-SAT といいます．例えば次の論理式を充足するか？という問題は $3$-SAT であり， $x_1=\mathrm{True}$, $x_2=\mathrm{False}$, $x_3 = \mathrm{True}$, $x_4 =\mathrm{True}$ などで充足可能です．
$$(x_1\lor\lnot x_2\lor x_3)\land(\lnot x_3\lor x_4 \lor x_1)\land(\lnot x_2 \lor \lnot x_4)$$
ここで， $n$ 変数 $m$ 節の $k$-SAT に対し， $s_k$ を次のように定めます．
$$s_k = \mathrm{inf} \lbrace \delta_k | k{\rm-SATを解く} 2^{\delta_kn}\mathrm{poly}(m){\rm 時間アルゴリズムが存在する}\rbrace $$
問題の包含関係から，
$$s_3\leq s_4 \leq \dots$$
となることに注意して，ETH(Exponential Time Hypothesis:指数時間仮説)の主張は $s_3>0$ です．
また，$k$-SAT に対しては$\left(2-\frac{2}{k+1}\right)^n\mathrm{poly}(n,m)$時間アルゴリズムが知られており[5]，$s_k<1$ を満たすことがわかります．$s_k$ は単調増加し上に有界なので，ある値に収束します．その値が1である，すなわち $s_\infty=1$ であるという仮定が SETH(Strong Exponential Time Hypothesis:強指数時間仮説) です．
Orthogonal Vectors Problem
LCS の計算量の下界を示すため， Orthogonal Vectors という問題を経由します． Orthogonal Vectors Problem $OV_{N,m}$は$ y_1,\dots, y_N, z_1,\dots, z_N\in \lbrace 0,1 \rbrace^m$ が与えられるので，ペア$(i,j)$で内積 $y_i\cdot z_j=0$ を満たすものが存在するかを判定する問題です．
この問題について，SETH の下で， ${}^\forall \delta > 0$ に対し， $OV_{N,m}$ の $O(N^{2-\delta})$ 時間アルゴリズムは存在しない(ただし， $m = \mathrm{poly}(\log n)$)ことが示せます．証明は $k$-SAT を $OV_{N,m}$ に帰着することによって行われます．
いま，$k$-SAT のインスタンスが $\phi$ が $m$ 個の節を持つ $n$ 変数の論理式であるとします($n$ が奇数の場合は式に現れない$n+1$番目の変数があると思ってください)．また，$N=2^{n/2}$とし， $m$ 個の節を $C_1,\dots,C_m$ とします．ここで，$x_1,\dots,x_{n/2}$ に対する変数の割り当て $a$ と $x_{n/2+1},\dots, x_n$ に対する変数の割り当て $b$ に対し， $y_a, z_b\in \lbrace 0,1\rbrace^m$ を次のように定めます．
y_a(i) = \left\{
\begin{array}{ll}
0 & \text{if } a \text{ が } C_i \text{ を充足する}\\
1 & \text{それ以外}
\end{array}
\right.
z_b(j) = \left\{
\begin{array}{ll}
0 & \text{if } b \text{ が } C_j \text{ を充足する}\\
1 & \text{それ以外}
\end{array}
\right.
CNF の節が $(x_1 \lor x_2 \lor \dots \lor x_k)$ のように $k$ 個以下の変数の論理和になっていることを考えると，$n/2$ 個の変数の割り当てを決めたとき，ひとつでも True となればその節は充足されるし，逆に節が充足されないときは残りの変数でその節を充足しなければならないことに注意してください．
このようにして$OV_{N,m}$ のインスタンス $y_1,\dots,y_N, z_1,\dots, z_N \in \lbrace 0,1\rbrace^m$ ができました．インスタンスの変換は $O(N\mathrm{poly}(m))$ 時間で行えます．$\phi$ の各節は $a,b$ どちらかの割り当てによって充足されなければならないことを考えると，ペア $(a,b)$ であって， $y_a\cdot z_b=0$ を満たすものがあることと，割り当て $a$ と $b$ によって $\phi$ が充足されることは同値です．
ここで，$OV_{N,m}$ を $O(N^{2-\delta})$ 時間で解くアルゴリズムが存在するとすると， $k$-SAT が $O((2^{n/2})^{2-\delta}) = O(2^{n(1-\delta/2)})$ 時間で解けることになります．$k$ は任意なのでこれは SETH に矛盾します．
LCS-Pair Problem
Orthogonal Vectors Problem を LCS に帰着する前に LCS-Pair Problem という問題について考えてみます．LCS-Pair Problem $LCS\text{-}Pair_{N,m}$ は文字列 $a_1,\dots,a_N, b_1,\dots,b_N \in \Sigma^m$ が与えられたとき， $\max_{i,j} LCS(a_i,b_j)$ を求める問題です．ただし，$LCS(a_i,b_j)$ は $a_i$ と $b_j$ のLCSの長さを表します．
LCS(Longest Common Subsequence:最長共通部分列)について，もう少し詳しく説明します．文字列$A = \langle a_1,\dots, a_m\rangle$ の部分列とは $1\leq i_1<\dots < i_k \leq m $ が存在して $A'=\langle a_{i_1},\dots, a_{i_k} \rangle$ のように表せるものを言います．さらに， 文字列 $A$ と $B$ のどちらの部分列でもあるような文字列を $A,B$ の共通部分列といいます． $A,B$ のLCSとは $A,B$ の共通部分列のうち長さが最長のもの(のうちひとつ)です．例えば， $A = 10011$, $B = 11001$ を考えると，$1001$ は $A,B$ に共通する部分列です． $A,B$ に長さ5の共通部分列は存在しないので， $1001$ は $A,B$ のLCS で $LCS(A,B)=4$ となります．
ここで， ある定数 $c$ が存在して，$OV_{N,m}$ は $LCS\text{-}Pair_{N,cm}$ に線形時間で帰着できることが示せます．
まず， $0_y = 10011, 1_y = 11100, 0_z = 11001, 1_z = 00111$ と定義します．$LCS(0_y,0_z)=4$, $LCS(0_y,1_z)=4$, $LCS(1_y,0_z)=4$, $LCS(1_y,1_z)=3$ となります．ここで重要なのは，$LCS(1_y,1_z)=3$ のみ長さが短いということです．これが$1\cdot 1=1$となり内積が 0 にならないことに対応します．
あとは各ベクトルを$0_y,1_y,0_z,1_z$ で置き換えていけばよいです．ただし，それぞれが変に対応づいてしまわないように間に無関係の文字を詰めます．$y_i$ に対応する文字列 $a_i = code_y(y_i)$ は $y_i$ の $0$ を $0_y$, $1$ を $1_y$ に変換しそれぞれを3つの$2$で区切って連結することで得られます． $z_j$ に対応する文字列 $b_j = code_z(z_j)$ も同様に得られます．例として， $y_i = 101$ と $z_j = 110$ とすると，
\begin{eqnarray*}
a_i = code_y(101) = 111002221001122211100 \\
b_j = code_z(110) = 001112220011122211001
\end{eqnarray*}
となります．インスタンスの変換はこれで完了です．
まず，得られる文字列の長さは $m'=8m-3$ となります．したがって，変換後の文字列の長さは $m$ の定数倍であり，この変換は線形時間で行えます．次に得られる LCS の長さについて考えてみます．$y_i\cdot z_j = 0$ である場合， 全ての 2 を対応付ける自然な方法で $S:=4m + 3(m-1) = 7m-3$ の長さの共通部分列が取れることが簡単に分かります．$y_i \cdot z_j \neq 0$ である場合は $LCS(y_i,z_j) < S$ であることが示せれば，$LCS\text{-}Pair_{N,m'}$ の答えが $S$ かそれ以下かで $OV_{N,m}$ の真偽が判定できそうです．
3つの2で仕切られた5文字の部分同士の LCS は最大4です．したがって，2を捨てなければ（必ず対応づけることにすれば）任意の$1\leq i,j \leq N$ について $LCS(a_i,b_j)\leq S$ です．特に，$y_i\cdot z_j \neq 0$ なら区切られた区間の LCS が3になる箇所が存在するので $LCS(a_i, b_j) < S$ です．$a_i$ の3つの2が対応づかない場合を考えます．これは $a_i$ から いくつかの2を削除することと同じです．連続する3つの2を削除すると区切られていた $0,1$ からなる2つの区間が繋がりますが，その区間はすべてLCSに含まれるものとしましょう．例えば，
\begin{eqnarray*}
a_i = code_y(101) = 111002221001122211100 \\
b_j = code_z(101) = 001112221100122200111
\end{eqnarray*}
について，1番目の222を使わないことにすると， $a_i' = 11100\text{ }1001122211100$ となり $11100\text{ }10011$ の部分はLCSにどのように含まれるかわからないので，全てLCSに含まれることにして上から抑えようということです．$a_i$ から222を $k$ 個捨てるとき，222で区切られた区間で長さが5であるようなものの数を $\ell$ とします．ひとつ222を消すことで2つの区間が結合することを考えれば $\ell \geq \max(m-2k,0) \geq m-2k$ となります．したがって，このとき
\begin{eqnarray*}
LCS(a_i', b_j)&\leq& 5(m-\ell)+4\ell + 3(m-1-k)\\
&=& 7m-3-3k+m-\ell\\
&\leq & 7m-3-3k+m-(m-2k)\\
& = & 7m-3-k
\end{eqnarray*}
となります．したがって，いくつかの222を $a_i$ から削除し $a_i'$ とすると $LCS(a_i',b_j) < S$ となることがわかりました．また， 222 を 全て対応させるときの共通部分列の長さは明らかに $S$ 以下なので， $y_i\cdot z_j=0$ のとき $LCS(a_i,b_j) = S$ であることもわかります．
以上から $LCS\text{-}Pair_{N,m'}$ の答えが $S$ であるとき，かつそのときに限り $y_i\cdot z_j = 0$ なる $i,j$ が存在することがわかりました．これで $OV_{N,m}$ から $LCS\text{-}Pair_{N,m'}$ への帰着は完了です．
LCS
LCS Problem はここでは2つの文字列が与えられたとき，そのLCSを求める問題です（一般には，入力文字列の個数が任意であることもあります．その場合は全ての文字列に共通する部分列のうち最長のものを求めます）．
ここからは， $OV_{N,m}$ を LCS Problem に帰着することを考えます．示したいのは SETH の下で任意の $\delta >0$ に対し， 長さ $n$ の2つの文字列を入力にとる LCS Problem を解く$O(n^{2-\delta})$ 時間のアルゴリズムが存在しないということです．方針は LCS Pair Problem のインスタンスをひとつの文字列の組に集約することです．
$code'_y(y_i)=code_y((y_i,0))$, $code'_z(z_j)=code_z((z_j,1))$, $E = code_y((0^m,1))$ を定義します．ただし，
y=(y_{1}, \dots, y_{m})^T
に対して，
(y,0)=(y_{1}, \dots, y_{m},0)^T
を意味します．$(z,1)$ や $(0^m, 1)$ についても同様です．ここで，$y_i\cdot z_j = 0$ であるなら$(y_i,0)\cdot (z_j,1) = 0$ となり， 任意の $j$ について $(0^m,1)\cdot (z_j,1) = 1$ となることに注意してください．
$m''=8m+5=|code'_y(y_i)|+1$ として， $a_i, b_j$ を次のように定義します．
\begin{eqnarray*}
a_i &=& code'_y(y_i)3^{m''}E\\
b_j &=& 3^{m''}code'_z(z_j)3^{m''}
\end{eqnarray*}
$a_i,b_j$ の LCS を考えると，$3^{m''}$ の部分は捨てるわけにはいかないことがわかります．したがって,
$$LCS(a,b) = m'' + \max( LCS(code'_y (y_i), code'_z (z_j)) , LCS(E, code'_z (z_j)))$$
になります．ここで，
LCS(code'_y (y_i), code'_z (z_j)) \begin{cases} = S + 7 & (y_i\cdot z_j=0) \\ \leq S + 6 & (y_i\cdot z_j \neq 0) \end{cases}
LCS(E, code'_z (z_j))) = S+6
より，
LCS(a_i,b_j) = \left\{
\begin{array}{ll}
m''+S+7=:S' & \text{if } y_i\cdot z_j = 0\\
m''+S+6=S'-1 & \text{if } y_i\cdot z_j \neq 0
\end{array}
\right.
が成り立ちます．
次に，これらの $a_i$ や $b_j$ を連結していって一つの文字列のペアを得ます．文字列 $A,B$ を次のように定義します．
\begin{eqnarray*}
A&=&a_14^{\ell}a_24^{\ell}\dots4^{\ell}a_N4^{\ell}a_14^{\ell}a_24^{\ell}\dots4^{\ell}a_N\\
B&=& 4^{N\ell}b_14^{\ell}\dots4^{\ell}b_N4^{N\ell}
\end{eqnarray*}
インスタンスの変換はこれで完了です．ただし， $\ell$ は $m$ の定数倍です．
この $A, B$ の長さは $O(Nm)$ となります．インスタンスの変換も同様に $O(Nm)$ で行えます．得られる LCS の長さについても考えてみます．$y_i\cdot z_j=0$ なる $i,j$ が存在する場合， $-j<k\leq N-j$ について $y_{(i+k) \bmod N}$ と $z_{j+k}$ を対応させるようにすれば，$A$ の $4^\ell$ の部分も全て対応が取れて長さ $S'':=N(S'-1)+1+(2N-1)\ell$ の共通部分列が存在することがわかります．すなわち， $y_i\cdot z_j=0$ なる $i,j$ が存在する場合， $LCS(A,B) \geq S''$ です．あとは$y_i\cdot z_j=0$ なる $i,j$ が存在しない場合， $LCS(A,B) < S''$ が言えればよいです．
いま，$y_i\cdot z_j=0$ なる $i,j$ が存在しないことを仮定します．まず，$A$ に含まれる $4^\ell$ が全てLCSに含まれる場合を考えます．このとき，$A,B$ の共通部分列は $a_i$ に連続するいくつかの $b_j$ を割り当てて得られる共通部分列を足し合わせたような形になっています．任意の$i,j$ について $LCS(a_i,b_j) = S'-1$ を満たすかつ 文字列 $B$ の $b_{j'}$ で表現される部分は 文字列 $A$ の $a_{i'}$ で表現される部分より少ないので，1つの $a_i$ に複数の $b_j$ を割り当てる意味はありません($|a_i|= 3(8m+4)+1$, $S' = 8m+5+7m-3+7$ なので $2(S'-1)> |a_i|$ となるため)．よって，$N$ 個の $a_i$ で表される部分と $N$ 個の $b_j$ で表される部分が対応するのが最適で， 長さ $(2N-1)\ell + N(S'-1)=S''-1$ となります($LCS(a_i,b_j)=S'$ なる $i,j$ が存在しない場合を考えていることに注意)．
次に，$A$ に含まれる $4^\ell$ のうちいくつかが共通部分列に含まれない場合を考えます．$4^\ell$ の部分が1つ無くなると，ある$i$ について $a_i,a_{i+1}$ を独立に扱わなくて良くなるので， ここに 2種類の $z_j$ からなる部分を対応させて高々長さ $2(3(8m+4)+1) - 2(S'-1)$ の部分を共通部分列に含めることができます．しかし，$4^\ell$ の部分を削除しているので， 高々$m$ の定数倍の得は相殺されてしまいます．したがって，$\ell$ を適切に選ぶことで $LCS(A,B) \leq S''-1$ を満たすようにできます．
これで， $y_i\cdot z_j=0$ なる $i,j$ が存在しないときに，$LCS(A,B) \leq S''-1$ が成り立つことがわかりました．
したがって，$LCS(A,B) \geq S''$ であるかどうかによって，$OV_{N,m}$ を判定することができました．LCS Problem が $O(n^{2-\delta})$ 時間で解けるとき， $OV_{N,m}$ は $O((Nm)^{2-\delta})$ で解けることになります．ここで， $m = \mathrm{poly}(\log n)$ であれば $OV_{N,m}$ の下界に反し SETH に矛盾します．
ここでは，文字種類数が定数の LCS Problem の下界について説明しましたが，文字種類数が定数の場合はバイナリ文字列に帰着できるようです[1]．
まとめ
ETH, SETH の定義を示し， Orthogonal Vectors Problem を経由して，SETH の下で LCS の改善困難性を示しました．
参考文献
- Paul Beame. "Lecture 17: The Strong Exponential Time Hypothesis." 2016.
https://courses.cs.washington.edu/courses/cse531/16wi/lectures/lect17.pdf - Weiyun Ma, Joshua Brakensiek. "Lecture 17: The Strong Exponential Time Hypothesis." 2019.
https://web.stanford.edu/class/cs354/scribe/lecture17.pdf - 脊戸 和寿. "Strong Exponential Time Hypothesis."
https://art.ist.hokudai.ac.jp/~seto/misc/seth.pdf - Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010.
- Dantsin, Evgeny, et al. "A deterministic (2− 2/(k+ 1)) n algorithm for k-SAT based on local search." Theoretical Computer Science 289.1 (2002): 69-83.
おまけ
今回は Acompany にあまり関係ない記事でしたが，Acompany により関係する技術についてはAcompany 技術ブログで扱っています．この記事をここまで見てくださったあなたが面白いと思うであろう記事が沢山あります．
下記のページから，弊社への応募ができます．非常に働きやすいのでオススメです．