はじめに
サヴィッチの定理とは、$f(n)\in \Omega(\log(n))$である任意の関数$f$1について、
\begin{equation*}
\textrm{NSPACE}(f(n))\subseteq\textrm{DSPACE}(f(n)^2)
\end{equation*}
が成り立つことを示す定理です。
$\textrm{PSPACE}=\textrm{NPSPACE}$をも示せるけっこうすごい定理なんですが、あんまり知られてないように思います。
定理の証明を説明し、そこから系として$\textrm{PSPACE}=\textrm{NPSPACE}$を示します。
今回は、その証明に登場するSTCON問題について説明していきます。
STCON問題
STCON問題（S-T CONnectivity）とは、有向グラフ$G(V, E)$と頂点$s, t\in V$が与えられた時、$s$から$t$への経路が存在するかどうかを判定する決定問題です。
STCON問題の答えは、頂点$s, t$を引数に取り、$s$から$t$への任意の長さ（ここでは、重みなし有向グラフと考えて、辺の数）の経路の有無を返す関数によって与えられます2。
この関数を、$\textrm{stcon}(s, t)$とします。
では、STCON問題に関する性質を考えます。
- $s$から$t$への経路が存在するとして、その経路長は最大でも$|V|-1$になる。
- 同じ頂点を複数回訪問する必要がないから。辺が0本のとき、その経路は1頂点を含み、以降辺が1本増えるごとに経路に含まれる頂点が1つずつ増えていく。すべての頂点を含むとき、経路に含まれる辺の数が最大。
経路長制限のついたSTCON問題
発想
唐突ですが、ここでSTCON問題の部分問題を考えましょう。
それは、STCON問題に、「経路に含まれる辺の数の上限」を付け加えた問題です。
これを便宜上、この記事内に限ってsub_STCON問題と言うことにします。
$\textrm{sub_stcon}(s, t, k)$という関数を、$s$から$t$までの辺の数が$k$以下の経路が存在するかどうかを返すものと定義します（$k\in\mathbb{N}_{0}$）。
なお、経路長の上限から、$k\ge |V|-1$のとき、$\textrm{sub_stcon}(s, t, k)$は$\textrm{stcon}(s, t)$と同一になります。
つまり、$\textrm{stcon}(s, t) = \textrm{sub_stcon}(s, t, |V| – 1)$です。
では、$G$内の頂点$s_{0}, t_{0}$について、$s_{0}$から$t_{0}$への経路が存在するかどうか、つまり、$\textrm{stcon}(s_{0}, t_{0})$を、$\textrm{sub_stcon}$を使って求めましょう。
細かい説明は後回しになってしまうのですが、すごくざっくり言うと、計算空間の削減のため、$s_{0}$から$t_{0}$までの経路の、（存在するとして）だいたい中間地点を再帰的に見つける処理を行うために、sub_STCON問題を考えるのです。
定義
$\textrm{sub_stcon}(s, t, k)$を以下のように、再帰的に定義します。
なお、$\lfloor x\rfloor$、$\lceil x\rceil$は、それぞれ実数$x$に対する床関数と天井関数です。
- $k = 0$なら、$s$と$t$が同じときTrue、異なるときFalseを返す
- $k = 1$なら、$s=t$か、$s$から$t$へ延びる辺が存在すればTrue、しなければFalseを返す
- $k \ge 2$なら、以下の両方がTrueであるような頂点$u$が存在すればTrue、しなければFalseを返す
- $\textrm{sub_stcon}(s, u, \lfloor\frac{k}{2}\rfloor)$
- $\textrm{sub_stcon}(u, t, \lceil\frac{k}{2}\rceil)$
$k=0, 1$のときはだいたいイメージつくと思います。正の整数$n$に対して、$\lfloor\frac{n}{2}\rfloor$は最小値$0$、$\lceil\frac{n}{2}\rceil$は最小値$1$であることから、関数$\textrm{sub_stcon}$関数は無限ループには入りません。
$k\ge 2$のときは、だいたい「中間」にある頂点$u$を探索します。
「中間」の頂点というのは、$s, t$の両方からそれぞれ半径が約$\frac{k}{2}$以内の頂点のことです。
STCON問題の空間計算量
以上のように定めると、$\textrm{sub_stcon}$関数を再帰的に呼び出すごとに、$k$がおよそ半分になります。
関数呼び出しの「深さ」を考えると、$O(\log_{2}k)$になることがわかります。
なお、$k$は$|V|-1$以上あれば、元の問題と同じであることも踏まえると、関数呼び出しの深さは、$O(\log|V|)$程度です。
では、これらの操作にどれだけの領域が必要かを考えましょう。
補足しておくと、グラフを表現するのに例えば隣接行列を用いるとすると、その要素数は$|V|^{2}$ですが、このような問題の入力や前提は、計算に必要な領域としては数えないことになっています。
$k=0$のとき、これは入力された頂点に振ってある番号や記号を見て、等しいかどうかを見るだけなので、$O(1)$の大きさの領域しか必要としません。
$k=1$のとき、これも入力に与えられた隣接行列を参照すればいいので、$O(1)$の大きさの領域で計算できます。
$k\ge 2$のとき、各「深さ」では、いわゆるコールスタックの要領で、マシンのテープに関数の引数やローカル変数を記録します。
このとき記録が必要な値は、
- $s$ – 始点
- $t$ – 終点
- $k$ – 経路長制限
- $u$ – ローカル変数。「中間」頂点の候補。
で、それぞれの値は、$s, t, u$は頂点の番号、$k$もSTCON問題を解くにあたっては高々$|V|-1$で十分なことを思い出します。
すると、頂点を2進法で識別可能な桁数も考えて、$O(\log_{2}|V|)$の空間があればよいとわかります。
さて、$O(\log|V|)$の深さレベルそれぞれで、$O(\log|V|)$の記憶領域が必要だとすると、これは$O((\log|V|)^{2})$の領域があれば解けます。
以上より、STCON問題は、頂点数を$n$とすると、$O((\log n)^{2})$の領域があれば、決定性チューリングマシンで解けます。
次回
次回は、STCON問題を非決定性チューリングマシンで解いた時の空間計算量について検討していきます。
コメント