数理解析研究所講究録
第 716 巻 1990 年 71-80

71

推論の並列化
九州大学理学部基礎情報学研究施設
宮野悟

Satoru MIYANO

1

はじめに推論を並列に行うことができれば,しかし,より速く結論を得られると考えるのは自然である.

どの程度高速に結論を導き出すことが可能なのであろうか. 次の推論規則を例にとろう.
$A_{1}$$arrow$$A_{9}$$arrow$$A_{a}$$arrow$$A_{b}$$arrow$$A_{c}$$arrow$$A_{d}$$arrow$$\ovalbox{\tt\small REJECT}_{e}$$arrow$$A_{f}$$arrow$$A_{2}$$arrow$$A_{1},$ $A_{9}$$A_{3}$$arrow$$A_{2},$ $A_{a}$$A_{4}$$arrow$$A_{3},$ $A_{b}$$A_{5}$$arrow$$A_{4},$ $A_{c}$$A_{6}$$arrow$$A_{5},$ $A_{d}$$A_{7}$$arrow$$A_{6},$ $A_{e}$$A_{8}$$arrow$$A_{7},$ $A_{f}$例1
ここで,矢印の右側が空である推論規則の左のものを公理ということにする.

$A_{1},$ $A_{9},$ $A_{a},$ $A_{b},$ $A_{c},$ $A_{d},$ $A_{e},$ $A_{f}$が公理である. 公理に推論規則を次々に適用して得られるものを定理というが, 上の例では, すべての $A_{t}(t\in\{1, \ldots, 9, a, \ldots, f\})$ が定理である.

であることを示す証明木は図 1 のようになるが,れている.

並列に推論が可能であったとしても,とができないようにみえる.

ここでは,$A_{\overline{s}}$$A_{s}$

が定理を導き出すために, 7 段の推論が行わこの例ではより短い段数で結論を出すここの様な例に対しては, 並列化は役に立たないのであろうか.

ここでは, 推論を並列に行うことができるとき, その推論の体系を変換することにより,より高速に結論を導き出すことが可能なことを示す.
ディアは [5], [10], [11] によるが,この推論規則の変換法の基本的アイ

この方法は, 問題の中に潜在している自明でない並列性を抽出するのに極めて有用である. 第 3 節では, いくっかの例によりその有用性を確かめる.

72

図 1:

2

$A_{8}$の証明木バランス化による効率化
推論システムは組 $Q=(X, R)$ で与えられる.

ある.
る.

推論規則は

特に$\alphaarrow$$\alphaarrow\beta_{1},$の形をしている.

$\beta_{n}$$\ldots,$の形のとき, 文$X$$\alpha$は文の有限集合,

$R$

ただし,

$\beta_{n}\in X(n\geq 0)$$\alpha,$$\beta_{1},$$\ldots,$は推論規則の集合でを公理とよび, 公理の集合を axiom $(Q)$ とかく.

TH $(Q)$ は公理を含み, 推論規則に関して閉じている最小の集合である.の条件を満たす $X$ の最小の部分集合である. TH $(Q)$ の要素を定理と呼ぶ.

1. axiom $(Q)\subseteq TH(Q)$ .
$\beta_{n}\in TH(Q)$ かっ2.
$\beta_{1},$の推論木とは,る: もしラベルして持つならば$\alpha$$X$$\beta_{n}\in R$$\alphaarrow\beta_{1},$$\ldots,$$\ldots,$$Q$であならば,$\alpha\in TH(Q)$すなわち, 次である.の要素を頂点のラベルとする有限木 $T$ で次の条件を満たすものであのっいた頂点が,$\alphaarrow\beta_{1},$$\beta_{n}$$\ldots,$ラベルである.

$\beta_{1},$$\beta_{n}$$\ldots,$

のっいた

$n$

個 $(n\geq 0)$ の頂点を子と推論木 $T$ の頂点の個数および高さを,それぞれsize $(T)$ および height(T) で表す.
葉のラベルが全て公理である推論木を証明木とよぶ. 定理 $\gamma\in TH(Q)$ に対して,のラベルとする証明木 $T(\gamma)$ が存在することは明らかであろう.

$\gamma$を根

このとき,size $( \gamma)=\min$ { $size(T(\gamma))|T(\gamma)$ は の証明木},size $(Q)= \max\{size(\gamma)|\gamma\in TH(Q)\}$$\gamma$と定義する.
各推論規則$\beta_{1},$$\beta_{2}$)$\alphaarrow\beta_{1},$$\ldots,$$(\gamma_{2}arrow\gamma_{1}, \beta_{3}),\ldots,$$,$$\beta_{n}(n\geq 3)$に対して, 新しい文\gamma 1, ...,$(\alphaarrow\gamma_{n-2}, \beta_{n})$に置き換える.

2$\gamma_{n-2}$を用いてこれを$(\gamma_{1}arrow$

この置き換えにより, 推論規則の73
これにより, 以後は, $Q=(X, R)$ の推論規則の左側は個数は線形的にしか増加しない.
高々 2 っの文しかないと仮定する.

与えられた推論システム $Q=(X, R)$ から次のようなバランス化推論システムを構成する.

$(X^{B}, R^{B})$$X^{B}=X\cup(X\cross X)\cup(X\cross(X\cross X))$ である.

$R^{B}$$Q^{B}=$は次のものからなる.

1.

$R$の推論規則に対して,それぞれ $R^{B}$ の推論規則を次のように定義する.

2. $xarrow y,$ $(y, x)$
3. $(y, x)arrow z,$ $(z, (y, x))$
4. $(z, x)arrow(z, y),$ $(y, x)$
こうして構成される推論システム
か増加していない.

この$Q^{B}$の文の個数および推論規則の個数は多項式的にしに対して次の 2 っの命題が成立する.

命題 1

TH $(Q)=TH(Q^{B})\cap X$ .

命題 2$\gamma\in TH(Q)$に対して,$Q^{B}$

を $Q$ の定理とする.

バランス化推論システム$Q^{B}$

このとき,における$\gamma$$Q$における$\gamma$の任意の証明木$T(\gamma)$

証明木 $T’(\gamma)$ で

height $(T’(\gamma))\leq 7\cdot\log(size(T(\gamma)))$を満たすものが存在する.
命題 1 は構成から明らかである. 命題 2 の証明は次の補題を必要とする.

補題 3$T$を$k$分木とする.

このとき,size $(T’)<k/(k+1)size(T)$$size(T”)<k/(k+1)size(T)$を満たすような $T$ の頂点
る$T$

証明の部分木で,が存在する.

ただし,size $(T)$ は葉の個数である.

$T’$ は$v$におけは $T$ から $T’$ を取り除いてできる部分木である.

$T^{u}$

略.

命題 2 の証明
で,$v$$x,$根のラベルがのをいう.

(1)$y\in X$ とする.
$x$

$Q$

における仮定, 葉の中の 1 っがラベル

このとき,$y$

3

での $x$ の部分証明木とは,$Q$の推論木

で他の葉のラベルは全て $Q$ の公理であるも次の (1), (2) は同値である.

$(y, x)$ が $Q^{B}$ の定理である.

$y$

74
(2)

$Q$

における仮定正整数 $m$ に対して,$y$の部分証明木が存在する.

での $x$$S_{1}(m),$ $S_{2}(m)${(3)$S_{1}(m)=$ $x\in X|$(4)$S_{2}(m)=\{(y, x)\in X\cross X|$を次のように定義する.

サイズが高々 $m$ の $Q$ における$x$の証明木がある}.

サイズが高々 $m$ の $Q$ における仮定$y$での $x$ の部分証明木がある}.
このとき, $H(m)$ を$H(m)= \max\{height_{Q^{B}}(\alpha)|\alpha\in S_{1}(m)\cup S_{2}(m)\}$と定義する.
ある.
り,

また,サイズが 1 の証明木をもっものは,$Q$の公理だけであるので, $H(1)=0$ でサイズが 2 の証明木をもっものは $R$ の推論規則 $xarrow y$ から得られるものであ

このとき $(y, x)$ は $Q^{B}$ の公理であるので, $H(2)=0$ である.

そして, $H(3)=1$ となる.

$H(m)$ を評価するため次の 2 っの場合を考える.

1. $x\in S_{1}(m)$ としよう. このときサイズが高々 $m$ の補題 3 より,$T$の頂点

$y$

で,

$T_{1}$

を $T$ の$y$

$Q$におけるを根とする部分木とし,$x$の証明木 $T$ がある.

$T_{2}$

を $T$ から処の根を除いて男を取り除いてできる部分木とするとき,sizeとなるものが存在する.
ことから,$Q^{B}$$(T_{1})< \frac{2}{3}m-$,size$(T_{2})< \frac{2}{3}m$

よって, $x\in S_{1}((2/3)m),$ $(y, x)\in S_{2}((2/3)m)$ である.の推論規則 $xarrow y,$ $(y, x)$ を使い$H((2/3)m)+1$ のものがある.

$Q^{B}$における$x$の証明木で高さが高々したがって$H(m)\leq H((2/3)m)+1$となる.

図 2: $Q$ における仮定

4$z$

での $x$

このの部分証明木

$7\cdot\cdot 5$

2. $(z, x)\in S_{2}(m)$ としよう.

このときサイズが高々 $m$ の $Q$ における仮定

分証明木 $T$ がある. そこで葉 z‘から根\x へいたる道を考える.
どっていくとき size $(T_{1})>size(T)/2$ となる初めての点をを根とする $T$ の部分木である.

る部分木からする部分木,$z$$T_{4}$とする.のとりかたより図 2 のようになり,を根とする部分木を取り除いだもの,

もし$y_{2}$での $x$の部$z$からへた

ただし,$T_{2}$を$y_{1}$があれば乃を$x$$T_{1}$

は $y$を根とす$y_{2}$を根とは $T$ から処を取り除いた木であるとするとsizeである.

$y$

$y$

この道を

$z$

$(T_{4}) \leq\frac{1}{2}m$,size$(T_{2}) \leq\frac{1}{2}m$

また明らかにsize $(T_{3})\leq m$である.

したがって,を用い,

図 3 のような$y_{2}$

については 1 で構成した高さが高々 $H((2/3)m)+1$ の証明木

$Q^{B}$の証明木を構成すれば $(z, x)$ の証明木となる.の高さは高々 $H((2/3)m)+4$ である.

そして, そよって$H(m)\leq H((2/3)m)+4$となる.

$H((2/3)m)+l$

図3 :$Q^{B}$における $(z, x)$ の証明木

以上のことから, $H(m)\leq H((2/3)m)+4$ となり,

5

この $H(m)$ の不等式を解くことにより

76

図 4: バランス化推論システムの証明木

例 1 の推論システムをバランス化したときの証明木である. 推論の段数が減っている.

$H(m) \leq 4\log_{\frac{3}{2}}m=\frac{4}{\log_{2}3-1}\log m<7\log m$を証明できる. 口
図 4 は, 例 1 の推論システムの図 1 の証明木に対応するバランス化推論システムの証明木の例である. 推論の総数は 2 倍になっているが推論の段数は減少している.

CRCW PRAM 上で多項式個のプロセッサを使って, TH $(Q^{B})$ を時間O(log(size(Q))) で計算できる (Algorithm 1).
命題 1, 2 より,

begin
for $k=1$ to $7\cdot\log(size(Q))$
pardo for eachifthen TH $(Q^{B})arrow TH(Q^{B})\cup\{\alpha\}$end pardo
end forend$\beta_{n}\in R^{B}$$\alphaarrow\beta_{1},$$\ldots,$$\{\beta_{1}, \ldots, \beta_{n}\}\subseteq TH(Q^{B})$

Algorithm 1: TH
一般的には,$(Q^{B})$size $(Q)$ は $|X|$ に関して指数的となるが,ることができるような $Q$ にたいしては,$O(\log n)$6

もし size $(Q)$ を多項式で押さえ時間の並列アルゴリズムとなる.

$7y$$\{Q_{i}=(X_{i}, R_{i})\}_{i\geq 1}$$\gamma\in TH(Q_{i})$を推論システムの族とする. ある多項式 $p(n)$ が存在して, 各定理

が size $(T(\gamma))\leq p(|x_{:}|)$ となる$Q_{i}$の証明木をもっとき,$T(\gamma)$

この族は多項式サイズであるという.
以上のことをまとめると次の定理になる.

定理 4$\{Q_{i}\}_{i\geq 1}$

式個のプロセッサ数を用いて CRCW PRAM により$n=|X_{i}|$3

このとき TH $(Q_{i})$ は, 多項を多項式サイズの推論システムの族とする.
$O(\log n)$時間で計算できる.

ただし,とする.

逐次アルゴリズムから並列アルゴリズムヘ
前節でのべた結果のおもしろい側面として, 逐次アルゴリズムを並列アルゴリズムに変ある問題が, 多項式サイズの推論システムの族に $NC^{1}$ 還元換できることがある. つまり,可能ならば,その問題は $NC^{2}$ に入ることがいえる.

このアイディアにより,いくつかの問題を並列化できる. 以下にそのおもな例を述べよう.

1. 2-Satisfiability Problem $(2SAT)[1],$ $[4]$ は, 多項式個のプロセッサの CRCW PRAM
により時間 $O(\log n)$ で計算可能である.
$S=\{\{\alpha_{1}, \beta_{1}\}, \{\alpha_{2}, \beta_{2}\}, \ldots, \{\alpha_{m}, \beta_{m}\}\}$$\{x_{1}, \neg x_{1}, \ldots, x_{n}, \neg x_{n}\}$.

$S$$=$$\alpha;,$$\beta_{1}\in$の充足可能性を判定するには, 次の unit resolution を行う多項式サイズの推論システム$X_{S}$

を $2SAT$ の instance とする. ただし,

$Q_{S}=(X_{S}, R_{S})$を構成すればよい.

$\{\{\alpha, \beta\}|\alpha, \beta\in\{x_{!}, \neg x_{1}, \ldots, x_{n}, \neg x_{n}\}\}$\cup {ロ}$Q_{S}$の推論規則は次のものである.
$arrow$$\{\alpha, \gamma\}$$arrow$$\{\alpha, \beta\},$ $\{\neg\beta, \gamma\}$$\{\gamma\}$$arrow$$\{\beta\},$ $\{\neg\beta, \gamma\}$$arrow$$\{\beta\},$$\square$

ここで$\alpha,$$\beta,$$\gamma$$(i=1, ..., m)$$\{\alpha_{i}, \beta_{i}\}$$\{\neg\beta\}$は $\{x_{1}, \neg x_{1}, \ldots, x_{n}, \neg x_{n}\}$ のリテラルである.

, 物が存在して, 次の (1) と, (2) もしくは (3) のどちらか一方が成立することである [3].
は $O(m)$ である.
そして $\square \in TH(Q_{S})\Leftrightarrow S\not\in 2SAT$ となる. size
このとき,$S$が充足可能でないことの必要十分条件は,$(Q_{S})$(1) すべての $1\leq i\leq k-1$ について,(2)$\{\gamma_{1}\}\in S$

かつ$\gamma_{k}=\neg\gamma_{1}$$\{\neg\gamma_{i}, \gamma_{i+1}\}\in S$.

(3) ある $1<j<k$ に対して$\gamma_{1}^{J}=\neg\gamma_{j}’=\gamma_{k}$7.

.

リテラルの列$\gamma_{1},$$\ldots$

78
2. 文脈自由言語の認識は例で説明しよう.

$G$$NC^{2}$で可能.

を次め生成規則より成る文脈自由文法とする.
$Sarrow SS,$ $Sarrow(S),$ $Sarrow()$ ,(と)ここで,ムは終端記号である. 記号列 $w=x_{1}\cdots x_{n}$ に対して, 推論システを次のように定義する.

$Q_{w}=(X_{w}, R_{w})$$X_{w}=${ $S[i,$ $j]|j-i$ は偶数, $0\leq i<j\leq n$ }.

入は(1) $x_{i+1}x_{i+2}=$(2) $x_{i}=$ (かつ$()$のとき, $S[i, i+2]arrow$ .

$x_{\dot{r}+1}=$) のとき, $S[i-1, j+1]arrow S[i, j]$ .

(3) $S[i, k]arrow S[i, j],$ $S[j, k]$ .
よりなる.

このとき,
$S[i, j]\in TH(Q_{w})\Leftrightarrow S\Rightarrow^{*}x_{i+1}\cdots x_{j}$となり, 族 $\{Q_{w}\}$ は定理 4 の条件を満たす.

3. 文脈自由言語のクラスとプッシュダウン. オートマトンによって受理される言語のクラスが一致することはよく知られている.

このプッシュダウン. オートマトンをさらに一般化したものに非決定性 auxiliary プッシュダウン機械 [2] がある.

これは, 2 方向入カテープ (左右両方向に動ける読み取り専用のヘッ ドのっいたテープ) をもっプッシュダウンオートマトンに, 読み書き可能な 1 本の作業用テープと書き込みのみ可能な出力テープが備わったものである. 全ての入力に対して, 出力テープに書かれる記号列が一意に決まるとき, 関数を計算するという.

クラス $AuxPDA(n^{O(1)}, \log n)$ は,多項式時間で走り, 作業用テープの領域を高々 $O(\log n)$ 使う (プッシュダウンスタッ
クおよび出力テープに領域の制限はない) 非決定性 auxiliary プッシュダウン機械によって計算可能な関数のクラスである.

このクラスは, 多項式サイズの推論システムを構成することで効率よく並列化可能である [7]となることが知られている [8], [9].

. 実際,

このクラスは,$AuxPDA(n^{O(1)}, \log n)\subseteq NC^{2}$

ソーティング,パターンマッチパージング等の関数を含んでいるとても広いクラスである.

ング,

4. 辞書式順序で最初の極大な独立点集合問題 (LFMIS) はにはいる [7].に制限すると,$P$完全であるが, 森 (forest)$NC^{2}$

森 $G=(V, E),$
$i\in V$える

$V=\{1, \ldots, n\}$, に対して推論システムを次のように構成する : 各に対して, $N(i)=\{\gamma|\{i, j\}\in E, j<i\}$ とする. 推論規則は次のように与:(1) 各 $j\in N(i)$ に対して,(2)$iarrow\neg j_{1},$$\neg j_{t}$$\ldots,$. ただし$\neg iarrow j$.

$N(i)=\{j_{1}, \ldots, j_{t}\}$8.

$7(J$

このとき, 頂点$i$が辞書式順序で最初の極大な独立点集合に属していることとこの推論システムの定理であることが同値となる. さらに,$i$がこの推論システムは, 多項式サイズである.

5. 完全グラフ$K_{4}$と同相 (homeomorphic) な部分グラフをもたないグラフに対して, 辞書式順序で最初の辺で生成される 3 サイクルなしの極大な部分グラフを求める問題
は $NC^{2}$ にはいる.

平面グラフで全ての頂点が 1 っの面上にあるものを外平面グラフ(outerplanar graph) という. 外平面グラフであるための必要十分条件は,$K_{2,3}$$K_{4}$およびに同相な部分グラフを含まないことが必要十分であるから, 外平面グラフに対しても, 同様のことがいえる.

このことも多項式サイズの推論システムを構成することにより示すことができる [6].

4

おわりに本稿で述べた並列化技法は, 問題の並列化に際し,考えられる.

–っの大域的な視点を与えるものと

しかし, 並列化に必要なプロセッサの数は多項式とはいえ,あまり現実的とはいえないだろう.

参考文献[1] Cook, S.A. and Luby, M.: A Simple Parallel Algorithm for Finding a Satisfying Truth
Assignment to a 2-CNF Formula, Inf. Process. Lett., Vol. 27 (1988), pp. 141-145.
[2] Hopcroft, J.E. and Ullman, J.D.: Introduction to Automata Theory, Languages, andComputation, Addison-Wesley $Publisl_{1}ing$ Company, 1979.
[3] Jones, N.D., Lien, Y.E. and Laaser, W.T.: New Problems Complete for NondeterminSpace, Math. Systems Theory, Vol. 10 (1976), pp. 1-17.
istic${\rm Log}$[4] Karp, R.M. and Wigderson, A.: A Fast Parallel Algorithm for the Maximal Independent Set Problem, J. $ACM$, Vol. 32 (1985), pp. 762-773.
[5] Miller, G. and Reif, J.: Parallel Tree Contraction and its Application, Proc. 26th IEEE
FOCS, 1985, pp.478-489.
[6] Miyano, S.: A Parallelizable Lexicographically First Maximal Edge-Induced Subgraph
Problem, Inf. Process. Lett., Vol. 27 (1988), pp. 75-78.

[7] Miyano, S.: Parallel Complexity and P-Complete Problems, Proc. Int. Conf. Ffth
Generation Computer Systems 1988, 1988, pp. 532-541.

980[8] Ruzzo, W.L.: Tree-Size Bounded Alternation, J. Comput. Syst. Sci., Vol. 21 (1980),
pp. 218-235.
[9] Ruzzo, W.L.: On Uniform Circuit Complexity, J. Comput. Syst. Sci., Vol. 22 (1981),
pp. 365-383.
[10] Rytter, W.: The Complexity of Two-Way Pushdown Automata and Recursive Programs, Proc. NATO Advanced Research Workshop on Combinatorial Algorithms onWords, Springer-Verlag, 1985, pp. 341-356.
[11] Rytter, W.: Parallel Time $O(\log n)$ Recognition of Unambiguous CFL’s, Proc. Fundamentals of Computation Theory (Lecture Notes in Computer Science, Vol. 199), 1985,
pp. 380-389.

10