数理解析研究所講究録
第 833 巻 1993 年 225-235

225

正論理関数の最大潜伏度について

The maximum latency of positive Boolean functions
牧野和久

Kazuhisa MAKINO

茨木俊秀

Toshihide IBARAKI京都大学工学部数理工学科

Department of Applied Mathematics and Physics,

Faculty of Engineering,
Kyoto University

Abstract The problem of finding an unknown vector of a partially defined Boolean function is pertinent
to such problems as identifying a Boolean function and learning from examples an underlying rule. This

paper introduces the concept of maximum latency for unknown vectors of a partial function obtained from a(completely defined) positive (i.e., monotone) Boolean function. Forof$n$class of general positive functions$tl\iota e$variables, it is known [8] that its maximum latency is greater than$\lfloor n/4\rfloor$

but not greater than$\lceil n/2\rceil$.

For the class of 2-monotonic positive functions, it is known [4] that its maximum latency is equal to 1. In
this paper, we obtain the following results for two classes of Boolean functions. (i) For the class of matroid
functions, its maximum latency is equal to 2. (ii) For the class of K-steiner tree functions of$l$nodes, ts$i$maximum latency is not greater than $l-|K|+2$ .
あらまし

不完全定義論理関数において未知ベク トルを発見する問題は, 論理関数の同定と密接に関連しており, またいくっかの例から一般的法則を導き出す帰納的学習においても重要な役割をもっ. 本報告では, 論

理関数を正関数に限定し, 不完全定義関数における未知ベク トルの発見の尺度として, 最大潜伏度の概念を導入する. 一般の$n$変数正関数のクラスについては, 最大潜伏度}xとが知られている [8].

$\lfloor n/4\rfloor$より大きく,$\lceil 7\sim/2\rceil$

以下であるこまた, 正関数のクラスを 2 単調正関数に限定すると, 最大潜伏度 $=1$ であることも知られている [4]. 本論文では, 正関数の 2 っのクラスにっいて, 以下の結果を得た. (i) マトロイ ド関数のクラスでは, 最大潜伏度 $=2$ である.

(ii) 1 節点の K- スタイナー木関数のクラスにっいては, 最大潜伏度は$l-|K|+2$ 以下である.

1

論理関数の定義域が,

まえがき

き,
$n$

変数ベクトル $x=(x_{1)}x_{2}, \ldots, x_{n})$ の関数 $f$ た$g$$\{0,1\}^{n}$の部分集合 $D$ であると

: $Darrow\{0,1\}$ を不完全定義論理関数 (partiallydefined Boolean function) という.

おいて, 各変数 $x_{\mathfrak{i}}(1\leq i\leq n)$ 及び関数値 $f(x)$ が$T(g)=\{x\in D|g(x)=1\}$:$F(g)=\{x\in D|g(x)=0\}$$0$

または 1 なる値のみをとるとき, すなわち,$\{0,1\}^{n}arrow\{0,1\}$であるとき,$f$$f$

を (完全定義) 論理関

数 ((completely defined) Boolean function) と言う.

と記し,

$a\in T(g)$$b\in F(g)$

を

$g$

を

$g$

の真ベクトル (true vector),の偽ベク トル (false vector),

さらに

226
$u\in\{0,1\}^{n}\backslash D$

3. $f(u)=1$ (あるいは ) に応じて, $a\in tnil\iota T(f)-$を未知ベク トル (unknown vector) と$0$$MT$ (あるいはいう.

$b\in 1\eta$(あるいは M

本論文では, 論理関数を正関数 (positive Boolean$MT:=MT\cup\{a\}$function, monotone Boolean function, 単調関数) にとする. 2 へ戻る.

限定して考察する. よく知られているように (2 章参照), 正関数 $f$ は, 極小真ベク トルの集合 min $T(f)$

が成立し,

$n$

$F(f)=$ { $b|$ ある $b’ \in\max F(f)$ に対して

$b\leq b’$}

極小真ベクトルの部分集合 $MT \subseteq\min$ $T(f)$である.

および極大偽ベク トルの部分集合 $MF \subseteq\max F(f)$

$T=$
$F=$

関数

$g$

の同定は完了している.

と出力長 $m$ ( $=|$ min $T(f)|+| \max F(f)|$ ) を基準に評価され,と $m$ の多項式オーダ時間で可能かど$n$うかが議論されてきた. 未知ベク
ると, ステップ 3 はIT に対して $a\geq a’$ }

$a|$

ある

$b|$

ある $b’\in IMF$ に対して $b\leq b’$$a’\in\lrcorner 1$}$n$

トル $u$ が一っ求まの多項式時間で実行できる ([4][7] [13]). 従って, ステップ 2 の未知ベク トルの発見$l$) ことの判定) が,アルゴリズム全体の複雑さを決定する鍵をにぎっている. 現在のところ, 正関数 $f$ がさらに 2 単調 (2-monotonic) であれば, ステップ 2 は多項式時間で実行できる.

したと $F\subseteq F(f)$ より $T\cap F=\phi$がって, その同定も多項式時間で可能であることがこのとき, 定義域 $T\cup F$ をもつ不完全定義

知られている [4]. 正しきい関数 (positive thresltold

とすると,
である.

{
{

$f$

(あるいは存在しなが与えられたとき,$:=MF\cup\{b\}$ )このアルゴリズムの複雑さは, 通常, 変数の個数

つまり,$T(f)=$ { $a|$ ある $a’\in$ min $T(f)$ に対して $a\geq a’$ }$F$

計算停止時, $MT=$ min $T(f)$ と M $F=$ lnax $F(f)$と極大偽ベク トルの集合 nlax $F(f)$ によって, 定義
される.

ax $F(f)-MF$ ) を求め,$T\subseteq T(f)$function) は 2 単調であるので [9] , この結果は正しを,きい関数の同定も多項式時間で可能であることも示
している.

$g(x)=\{\begin{array}{l}1,x\in T\text{のとき}0,x\in F\text{のとき}\end{array}$

しかし, 一般の正関数に対し,その同定が多項式時間で可能かどうかは, 現在のところまだ
と定め,

$f$

の部分関数 (partial function) と呼ぶ.

正関数 $f$ とその部分関数の概念は

$f$

の同定問題

(identification problem) ([7] [12]) と密接に関連している.
$f(x)$$f$の同定とは, 一部のベク

トル

$x$

の値を知る (所属性質問する) ことでに同定する問題であって,

に対する
$f$

を正確

いくっかの例から一般的

未解決な問題として残されたままである.
本論文では,

ステップ 2 の複雑さを示す一っの尺度として, 対象とする正関数の部分クラスについて,

その最大潜伏度の概念を導入し (詳しい定義は 2 章),
その値を評価する. 一般に,
ラス

$C$の最大潜伏度が$\Lambda_{C}(n)$法則を導き出す帰納的学習の一っの形態とも考えら$MT\cup MF$ に対して,れる ([1] [2] [6] [13]). 正関数 の同定手順の有力な(ただし,ものの一っは, っぎのような形に書かれる.

$x\in T\cup F$ を満足すれば,$f$

1. 適当な初期 $MT(\subseteq 1ninT(f))$ と M$(f))$

関数$F(\subseteq$

lnax $F$から始める.
$g$を一っ見っけ出す. 未知ベク トルが存在しなければ停止.

変数正関数のあるクであるとき, 各 a$\in$$||a-x|| \leq\bigwedge_{C}(?l)$

を満たす) すべてのベク

トル $x$ が$||y||= \sum_{1}^{n_{=1}}|y_{l}|$

クラス

$C$

の関数

$f$

の部分

において未知ベク トルは存在しないという性質がある. 例えば, 前述の 2 単調な正関数のクラス$2M$ を考えると,2. $MT$ と $MF$ で定まる部分関数 の未知ベク トル
$u$

$g$

$\uparrow l$

で [4],

最大潜伏度 $\Lambda_{2M}(7l)=1$ であるのステップ 2 は, $a\in MT\cup MF$ に対して,$||a-x||\leq 1$を満たすすべてのベク

トル

$x$

を調べる

ことで実現できる. この計算の手間は明らかに

$?l$

と

227

$m$

の多項式時間で可能であり, その結果,

$f$

の同定

も多項式時間で可能となるのである. しかし, 一般の $n$ 変数正関数のクラス

大潜伏度

$P$

を対象とするならば, 最$\Lambda_{P}(n)$定義 21

び $y=(y_{1)}y_{2}, \ldots, y_{n})$ において,に対して成立するならば,

特に, ある$j$$n$であるので [8], 同定アルゴリズムのステップ 2 を,をすべて調べることで実行するのでは, 多項式時間のアルゴリズムは得られない.
のような

$x$

の個数は

$n$

そ

の指数オーダ存在するからでこのことは, 一般の正関数の同定問題の困難ある.

さを示しており, 仮に多項式時間アルゴリズムが存在するとしても,$x_{\mathfrak{i}}\geq y$$1,2,$ $\ldots,$ $n$と記す.

式 (1.1) を満たす

変数ベク トル $x=(x_{1}, x_{2}, \ldots, x_{n})$ およ; が $i=$$x\geq y$ と記す.

に対して $x_{J}>yj$ が成立するとき $x>y$

口

(1.1)

[ $n/4\rfloor+1\leq\Lambda_{P}(n)\leq\lceil n/2\rceil$

$x$

$n$

次元 0-1 ベクトル全体の大小関係を図示したグラフをハッセ図といい,$H_{n}$と記す. ハッセ図 (Hasse

diagram) では, $a>b$ ならば,

を

$a$

$b$

の上に位置するように書き, 有向枝 $(b, a)$ を結ぶ. ただし $a>c$ ,$c>b$ を満たす$c$が存在するならば, 推移律によって明らかに $a>b$ であるので $a,$$b$

間の枝は省略する.

$n=4$ の場合のハッセ図を図 1 に示す.

その発見は容易ではないことを示唆している.
本論文では,

まず,

マトロイ

ド関数のクラスにおいて, 最大潜伏度 $=2$ であることを示し,

さらに,

グ

ラフ $G=(V, E)$ の K- スタイナー木関数のクラスにおける最大潜伏度は, $|V|-|K|+2$ 以下であることも示す.
以上の結果, マトロイ ド関数の同定問題は,

アル

ゴリズムのステップ 2 を, 各 $a\in MT\cup MF$ に対して,$||a-x||\leq 2$

を満たす

$x$

をすべて調べれば, 解くことができるので, 多項式時間で可能であることを示している.
なお, 正関数 $f$ の同定問題は,$f$の双対関数を求め

図1る問題とも密接に関連しており [11] (一方が多項式時間で可能ならば, 他方も多項式時間で可能である

ことを示せる),

したがってマトロイ ド関数の双対関数を求める問題に対する多項式時間アルゴリズム

定義 22 論理関数
$x,$

$y$

に対して,

$\angle l$$f$

次元ハッセ図において, 任意の入カベクトル$x\geq y$

ならば $f(x)\geq f(y)$ が成立するとき $f$ を正関数という.

口も存在する.
定義 2.$

2

正論理関数の最大潜伏度
本章では, 論理関数, 正論理関数, その部分関数,$f$を正関数, さらに $T(f)(F(f))$ を真ベク

トル (偽ベクトル) の集合とする.

$x\in T(f)$に対し,$y<x$ をみたす $y\in T(f)$ が存在しないならば,
$f$

$x$

は

の極小真ベクトル (minimal true vector) であると更に, 本論文のテーマである最大潜伏度を定義する.

いう. 極小真ベクトルの集合を min $T(f)$ と記す.

なお, 混乱が生じない限り, 論理関数を単に関数とた, $x\in F(f)$ に対し, $y>x$ をみたす $y\in F(f)$ が存記す.

在しないならば,$x$

まは $f$ の極大偽ベク トル (maximal

228
min $T(f)=$ {1100, 1001,0110} をもっ.

false vector) であるという. 極大偽ベク トルの集合

は,を $\max F(f)$ と記す.

その双対関数口$f^{d}$$=$$(x_{1}\vee x_{2})(x_{1}\vee x_{4})(x_{2}\vee x_{3})$$=$$x_{1}x_{2}\vee x_{1}x_{3}\vee x_{2}x_{4}$また,

定義より明らかなように, 正関数 $f$ の $\min T(f)$ で
は,

(

$x$

どの二っのベク トル$\leq x’$

$x$と $x’$ も比較司能ではないと $x’\leq x$ のどちらも成立しない). 逆に, 比{1100, 1010, 0101} をもつ. っまり,$\max F(f)=$ {0011, 0101, 1010} である. 口は min $T(f^{d})=$較可能なベク トル対を含まない集合 $S\subseteq\{0,1\}^{n}$ が与えられたとき, mill $T(f)=S$ によって正関数 $f$ を

定義 24 完全定義正関数

定めることができる.

よく知られているように (例えば [9]), 任意の論理関数は, いくっかの主項 (prime implicant) の論理和として表現することができる. 一般的にはこの表現は一意的ではないが, 正関数の場合は, すべての主

min $T(f),$
だし,

に対して,

$MT$

$MF \subseteq\max F(f)$ が与えられたとき$MT\cup MF\neq\phi$$arrow\{0,1\}$$f$), 不完全定義関数

を次のように定義し,

$f$

$g$

$\subseteq$(た: $T\cup F$の部分関数 (partial

function) であるという.

項を集めた完全論理和形 (complete sum) が唯一のも$g(x)=\{\begin{array}{l}1,x\in T\text{のき}0’ x\in F\text{のとき}\end{array}$のであることが知られている.

このとき, 正関数 $f$の各主項は否定リテラル元を含まず,

しかも, 次のよ

うに min $T(f)$ のベク トルと 1 対 1 に対応している.

ただし,{$F=$ {$T=$

すなわち, 各 $x\in$ min $T(f)$ において $x_{J}=1$ の要素に対応するリテラル x」の論理積を作ると,

これは $f$の主項であり, さらに任意の主項はこのようにして,

min $T(f)$ のベク トルから作ることができる. 換言すれば, 正関数 $f$ の完全論理和形は,T(ののベク$\min$

トルを主項という形に直して並べたものである. 完

である.

$f$

において,

$\min T(f)$(dual function)$f^{d}=\overline{f}(\overline{x})$

$f$

の双対関数

を求めることができれば,min $T(f^{d})( \max F(f^{d}))$ の各ベクトルの要素を$0$,

1 逆にすることによって max $F(f)( \min T(f))$ が得
たとえば mln $T(f)$ から min $T(f^{d})$られる. 従って,を求めることができれば, ただちに $\max F(f)$ を得ることができる.

$f$

の双対関数

べての演算について V を・に,の定数について$0$を 1 に, 1 をと言うこともできる.

$f^{d}$を$0$とは, 関数$\vee$

に,

$f$

$F)$

$f=x_{1}x_{2}\vee x_{1}x_{4}\vee x_{2}x_{3}$ある $b’\in MF$ に対して $b\leq b’$ }

$g$

に対して,

$u\in\{0,1\}^{n}\backslash (T\cup$を未知ベク トルといい, その集合 $U=\{0,1$

定義 26

$g$

を未知ベクトル集合という.

口を $MT$ と $MF$ によって定まる

$n$

変数正論

理関数 $f$ の部分関数とする. ある $a\in MT\cup MF$ に対して,$||x-a||\leq k$ を満たすベク トル $x$ の集合を $g$の $k$ 近傍という.
$g$

ただし,

の潜伏度 (latency)

整数$\lambda$$\lambda(g)$$||y||= \sum_{i=1}^{n}|y_{\dot{l}}|$である.

とは, 次め条件を満足する

をいう.

のす
$g$

またすべて

に入れかえた関数,

近傍に未知ベク トルは存在しなの $\lambda-1$

いが,$\lambda$

ただし,き,

例 214 変数正関数$b|$

定義 2.5 $f$ の部分関数と $\max F(f)$ は次のように関連している. すなわち,ある $a’\in MT$ に対して $a\geq a’$ }口$\}^{n}\backslash (T\cup F)$

全定義正関数$a|$近傍には未知ベクトルは存在する.
$g$に未知ベク トルが存在しないと$\lambda(g)=0$と定義する.

すなわち,$\lambda(g)=\min\{||x-a|||a\in MT\cup MF, x\in U\}$.

229
さらに, 正関数のある部分クラス$C$(maximum latency)

あらゆる$\Lambda_{C}(n)$とは,正関数 $f\in C$ とその部分関数

らに対する潜伏度$\lambda(g)$

変数関数,

$n$

変数

$n$

を考えたとき, それの最大値をいう. すなわち,$\Lambda_{C}(n)=\max\{\lambda(g)|f\in C$

f}よ

$g$

の最大潜伏度は $f$ の部分関数}に対して定義さ$\{Z_{x}|x\in m1_{11} T(f)\}$はこのマ トロイ ドの基底の集合を与える. その結果, マトロイ ドの定義より, あに対して, $|Z_{x}|=n-r$ が成立する.
ンク

K- スタイナー木関数のクラスの 3 種類を考え,$\Lambda_{C}(n)$$f$れる集合族 $\{Z_{x}|x\in T(f)\}$ はマトロイ ドであり,口

以下, 本論文では $C$ として, マトロイ ド関数のクラス,

変数マトロイ ド関数$n$る正の定数 $r(\leq n)$ が存在し, 任意の $x\in m1_{11}$ $T(f)$

,

$g$

すなわち,

の上界値と下界値を求める.

(rank) という.

マトロイ

この $r$ を $f$ のラド関数にはさまざまなクラスの関数が含まれており [3], 次の全域木関数
はその一例である.

定義 32 連結無向グラフ $G=(V, E)$ において, $E=$$\{1,2, \ldots n\}$例 224 変数正関数 $f=x_{1}x_{3}\vee x_{2}x_{4}$ は,と考え, 各 $i\in E$ に変数 ; を対応させる.
$x$

正関数 $f$ を

lnin $T(f)=$ {1010, 0101}$\max F(f)=$ {0011, 0110, 1001, 1100}

をもっ.

$f(x)=\{\begin{array}{l}1G_{x}=(V,I_{x})7)i\not\in k_{o}^{\pm}\propto)\xi g0G_{x}=(V,I_{x})7\}\dot{i}3\not\in\not\in!\oint_{\square }^{\pm}\emptyset\ \text{き}\end{array}$

このとき,function) [3] [5] という

0101}$MF=$ {0011,0110, 1001}$MT=$ {1010,と仮定すると,これを, 全域木関数 (spanningと定めたとき,miln $T(f)$ はこれによって定まる部分関数

$g$

の未

知ベク トルの集合は, 図 2 に示すように

表し,{1100}

である. 定義より,である.

3

この $g$ に対する潜伏度 $\lambda(g)$ は 2

る.

任意のベク

トル $x\in\{0,1\}^{n}$ に対し $Z_{x}=\{i|$$Xj=0,$ $j=1,2,$
$1,$

2,

)

$n$

$\ldots,$$n$} , $I_{x}=\{j|Xj=1,$ $j=$

} と記す. また, 集合$X$

に対し $|X|$ は $X$の要素数を表すものとする.

に対し,$\overline{a}=(\overline{a}_{1},\overline{a}_{2}, \ldots,\overline{a}_{\iota})$のランクは,$r=|V|-1$ である.

補題 31

変数マトロイ ド関数のクラス $M$ の最大$n$$\Lambda_{M}(n)$は次の条件を満たす.

$A_{M}(n)=1$$7l=1,2,3$ のとき$\Lambda_{M}(n)\geq 2$$n\geq 4$$n=1,2,3$ のとき,

か. 従って,$n\geq 4$のとき$A_{M}(7\sim)=1$のとき,$\lambda(g)=2$数マトロイ ド関数 $f$ とその部分関数
フ

$G$

$g$

の成立は明らをみたすと任意の$e:+e_{j} \in\min T(f)$存在するとき,$f$$i\in I_{\text{。}}(1)-I_{a^{(2)}}$であるような$a^{(1)}-$$j\in I_{a^{(2)}}-I_{\text{。^{}(1)}}$をマトロイ ド関数という.

口

が

変

に基づいて次のように定める.

(1) $\uparrow t=2k(k\geq 2)$ のとき.
$I_{a}$

は$2j-1,2j$ のどちらか一方のみを含む}$a^{(1)},$ $a^{(2)}\in$

に対して,

$n$

を図 2 のグラ$i$$\min T(f)$

である.

$f$

min $T(f)=\{a|$ すべての に対して

定義 31 $f$ が正関数であり, かっ任意の

た

全域木関数

証明
本章では, マトロイ ド関数の最大潜伏度を導出す.

だし, 集合 $X$ に対して $x*=\{\overline{a}|a\in X\},$ $a=$ド関数の最大潜伏度

マトロイ

口$( \max F(f))^{*}$ は極小力ットの集合を表す

潜伏度

口

ree

の全域木 (spanning tree) の集合を$G$$(a_{1}, a_{2}, \ldots, a_{n})$

$U=$

$t$

lllax $F(f)=\{b^{(j)}|j=1,2, \ldots, k\}$

ただし,
ある.

$b^{(j)}$,は $Z_{b^{(j)}}=\{2j-1,2j\}$ なるベク トルで

この $f$ に対して,

部分関数

$g$

を

230

例 3.1 $n=1$ の場合, 補題 3.

$lfT=l1\downarrow i_{I\downarrow}T(f)-\{0l01\cdots 0J\}$$\Lambda^{J}IF=11t$

axになる (図 3).

$l^{l^{\urcorner}}(f)$と定める. $u=010J\cdots 01$ とすると, 明らかに

未知ベク トルである.

また, 任意の

$j$

に対して,

}ま

$u+e_{2_{3}-1}\in T$

となり,

となる.

また,

任意の $a\in MT$ に対して,$u||=k,$$a\neq u$より,$||u-a||\geq 2$

一方, 任意の $b\in 1$)$’[\Gamma$$\mathfrak{l}\mathfrak{n}$

となる.

分関数

$g$

す

$MT= \min T(f)-\{0101\}${1010, 1001, 0110}
M $F=maxF(f)=$ {0011, 1100}$=$$||u-a||=2$ でについては, $||b||=n-2$である.

$|(n-2)-k|+2=k\geq 2$

それゆえ,

.

ax $F(f)=$ {0011,1 IOO}

$U=$$\geq$$f=x_{1}x_{3}\vee x_{1}x_{4}\vee x_{2}x_{3}\vee x_{2}x_{4}$であり, 9 は,と $u\not\leq b$ から,$||u-b||$は次のよう$||a||=||$

を満たし, とくに,

$a=u+e_{2g-1}-e_{2_{2}}\in MT$ については,$g$Inin $T(f)=$ {1010, 1001, 0110, 0101}$\uparrow\iota+$$\Lambda lT\cup\Lambda f\Gamma\cup\{u\}=\{0,1\}^{v\iota}$の $f$ となわち,をみたす. 従って,

$e_{2_{j}-1}\geq 1\downarrow+e_{2g-1}-e_{2y}\in MT$

ある.

$u$

$J$

{0101}

たしかに, 潜伏度\mbox{\boldmath $\lambda$}(g) $=2$ である.

口

このように構成した $f$ とその部

に対して,$\backslash (g)=2$が成立する.

(2) $\uparrow l=2k+1(k\geq 2)$ のとき.

$f$

は,

nlnn $T(f)=\{a|2k+\rfloor\in$ I。かっ, すべての に対$j$

して$I_{a}$(ま $2j-1,2j$のどちらか一方のみを含む}

lltax $F(f)=\{b^{(j)}|j=1,2, \ldots, k\}\cup\{11\cdots 10\}$をもつ.

部分関数 を$g$$MT=$ nlill $T(f)-\{0101\cdots 011\}$$MF= \max F(f)$によって定める.

このとき,$u=\{0101\cdots 011\}$は未知ベク トルとなり, (1) と同様に $\lambda(g)=2$ を示すことができる.

口

図 3 例 3. 1 の部分関数?
$r_{\triangleleft}^{3}2^{1}$

補題 32 マトロイ ド関数(1) n=2k のとき$MT\neq\phi$ かっ$2$$r_{\sim}^{3}2^{1}\triangleleft.$ .

.....

図2

$\lambda(g)=2$

$f$

の部分関数

, 各 a $\in MT$ に対して,をみたすすべての

$x$

$g$

において,

$||x-a||\leq$

が $T\cup F$ に含まれるならば,$MT=$ min $T(f)$ である.

)$\supset KO2k\sim$$2\underline{k+}l$

2

(2)

$b$

$...\supset r_{2k^{1}}^{k}$

証明

$k$

$n=2k+1$ のとき.

$b\in IltiI1$トル) が存在するとして矛盾を導く.
つ選び,を実現する全域木関数

T(f)–MT(すなわち,

$f$

ば,

$k=|I_{\text{。^{}(1)}}-I_{b}|$とする.

$||b-a^{(1)}||=2$ すなわち,

$b$

は未知ベク

$a^{(1)}\in MT$ を一もし, $k=1$ なら$b\in T\cup\Gamma^{J}$であり, 仮231
定 $b\in miuT(f)-MT$ に矛盾する.
らば,

$f$

もし, $k>1$ なはマトロイ ド関数より, ある$j\in I_{b}-I_{a^{(1)}}$に対して,$i\in I_{\text{。}}(\downarrow)-I_{b}$$a^{(2)}=a^{(1)}-e_{i}+e_{j}$ であるよ

うな $a^{(2)}\in miuT(f)$ が存在する. そのとき,$a^{(1)}||=2$ より,あり, さらに,$a^{(2)}\in T\cup F$

は$\lambda fT$, っまり,$a^{(1)},$ $a^{(2)},$に属する. それゆえ,であることに矛盾する.

$\cdots,$

このように$a^{(k)},$3.4 より, $c=b$ である. つまり, $b\in MF$ である.

補題 36

$n$

変数マトロイ ド関数の最大潜伏度$\Lambda_{M}(\iota)$

補題 32 と補題 3.5 より明らか.

証明

口

min $T(f)-MT$$b\in$

定理 31

口

$n$

変数マトロイ ド関数の最大潜伏度$\Lambda_{I}\backslash 4(\uparrow))$は次の条件を満たす.

(1) 任意の $a\in$ mln $T(f)$ と任意の $i\in I_{a}$ に対して,であるような$b\in$$\Lambda_{M}(n)=\{\begin{array}{l}1,n=l,2,3[oslash]\ \doteqdot 2,n\geq 4\emptyset\ \doteqdot\end{array}$max $F(f)$ が存在する.

補題 31 と補題 3.6 より明らか.

証明(2) 任意の $b \in\max F(f)$ と任意の $i\in Z_{b}$ に対して,$a-e_{j}\leq b$

口は A $M(n)\leq 2$ をみたす.

$a^{(k+1)}=$

補題 33 正関数 $f$ において,$b+e_{3}\geq a$$||a-(a-e_{J})||=1$ より,$c\geq a-e_{J}$ であるような $c\in MF$ が存在する. 補題$||a^{(2)}-$$a^{(2)}\in MT$ で$|I_{a(2)}-I_{b}|=k-1$ である.

して得られたベクトル列$b$とこの a に対して,である.

であるような $a\in$ min $T(f)$ が存在

以下では,$m_{1}=|mi_{I1}T(f)|$口, $m_{2}=| \max F(f)|$ ,$m=m_{1}+m_{2}$ とおく.

する.

証明

(1) $a-e_{j}\in T(f)$ ならば, $a \not\in\min T(f)$ に矛盾する. 従って,$a-e_{j}\in F(f)$ であり,

$j\in I_{b}$とすると,$b\geq a$り, 矛盾する. 従って,,$f$

. これより, $b+e_{j}\geq a$[10] 参照

証明は,より明らか.

口

補題 $3.7$

ランク$m_{2}\leq m_{1}r$が成立する.

証明

$r$

口

$f$

の部分関数

$g$

において,

ド関数

のマ トロイ

任意の $a\in$ min $T(f)$ に対して,$|\{a-e_{J}\cdot|j\in I_{\text{。}}\}|=r$

補題 3.5 マトロイ ド関数

マトと $m$ の多項式時間で同定される.

$n$

最大潜伏度が定数であることと, 1 章の議論

$b\geq a-e_{J}$ であるような $b \in\max F(f)$ がただ一つ存在する.

証明

$f$

口

において, 任意の $a\in$$miuT(f)$ と任意の $j\in I_{a}$ に対して,と $m$ の多項式時間で得られるならば,においを得る. (2) についても同様に示すことができる.

補題 3.4 マトロイ ド関数$n$

ロイ ド関数$b$つまり $a\in F(f)$ とな$j\not\in I_{b}$の答が$b\geq a-e_{j}$ であるような $b \in\max F(f)$ が存在する. このて,定理 3.2 もし, 所属性質問 (membership queries)

$f$

において,

$|I$

$|=r$ より,。

. 従って,$|\{a-e_{J}|a\in lninT(f);j\in I_{a}\}|\leq m_{1}r$$MT= \min T(f)$ , かっ, 各 $a\in MT$ に対して,$||x-a||\leq 1$ をみたすすべての$x$が $T\cup F$ に含まれるならば, M $F= \max F(f)$ である. すなわち,$g=f$ である.
証明

うな

口

定理 3.3

任意の $b \in\max F(f)$ を考える. 補題 3.3 (2)より, 任意の補題 34, 補題 33 (2) より $m_{2}\leq m_{1}r$ が成立する.

$a\in 1ni\iota\iota T(f)$に対して,$a-e_{j}\leq b$

であるよが存在する. 仮定より,$a\in MT$$j\in Z_{b}$$n$変数マトロイ ド関数 $f$ の完全論理和形が与えられたとき, その双対関数$n$と$m_{1}$

(

$=|$

ができる.

min $T(f)|$ )$f^{d}$の完全論理和形を,の多項式時間で求めること

232
証明

$f$

の完全論理和形より min $T(f)$ を得ることができるので, $MT=1ninT(f),$た,$MF=\phi$ とする.

mfin $T(f)$ を用いて, 所属性質問の答を

$n$

と

ま

マトロイ ド関数 $f$ は,$n$と $m(=m_{1}+m_{2})$の多項式時間で $\iota naxF(f)$ が得られる. 2 章で述べたように nlax $F(f)$ より, 双対関数

$f^{d}$の完全論理和形を求めることができる. 補題 3.7 より,$m_{1}$の多項式であり, 以上の計算は,式時間である.

$n$

と

$m$

$m_{1}$

は口

定理 4.1 もし, 全域木, 極小カット, 単純閉路のい$\uparrow n_{1}$の多項式時間で得ることができる. その結果, 定理
3.2 より,補題 41, 補題 3.7 より明らか.

証明

$n$

と

の多項

ずれかのリストが与えられたとき, その他のリスト
を $n,$$m_{1}$(すなわち, 枝数と全域木の数) の多項式時間で得ることができる.
証明

定理 33 と同様に示すことができる.

定義 4.2 枝数$n$

口の連結無向グラフ $G=(V, E)$ と夕 $-$ ゲット節点集合 (tlte set of target nodes) $K\subseteq V$$\square$が与えられたとき,$n$

変数 K- スタイナー木関数$(I\langle-$

steiner tree function) [3] [5] を次のように定義する.

4

グラフ論的関数の最大潜伏度
本章では, 全域木 (spanning$t$ree), 極小カット$f_{K}(x)=\{\begin{array}{l}1,G_{x}=(V,I_{x})(^{arrow}.kt\backslash \tau|f^{A}\prime\Leftrightarrow^{c}\emptyset i,j\in I\zeta\delta^{i}gf_{D}^{\pm}\text{のとき}0,<i\emptyset\{\llcorner|)\end{array}$(minimal cut), 単純閉路 (simple circuit) を表す関数とマトロイド関数の関係を示し, さらに, K- スタ

すなわち, min $T(f_{K})$ は $G$ における K- スタイナー

イナー木関数おける最大潜伏度の上界値を与える.

木の集合を表し,

定義 4.1 全域木関数 $f$ に対し, $fi(x)$ を次のように$(l\mathfrak{n}axF(fJ_{\backslash }\cdot))^{*}$

はターゲッ ト集合 $K$を分ける極小カッ トの集合を表す.

定義 4.3 グラフ $G=(V, E)$ とターゲット集合

定義する.

おいて,
$fv$
$fi(x)=\{\begin{array}{l}0_{)}\text{ある}\in m(f)\text{対して},x\leq a\text{のとき}l,\text{その他}\end{array}$K- スタイナー木関数を$f_{i\backslash ^{\sim}}$

と定める.

に

, 全域木関数をとするとき, 各 $a\in$ lnill $T(f_{K})$ に対して,$\{x|x\in lninT(f_{V}), x\geq a\}$$I\iota$$S_{a}=$

口

明らかに, lnax $F(fi)= \min T(f)$ であり, min $T(fi)$

補題 42 グラフ $G=(V, E)$ とターゲット集合 $K$ には $f$ が表すグラフの単純閉路の集合を表し, $F(fi)$ は対する, K- スタイナー木関数$f$が表すグラフの閉路を含まない枝集合の族を表す.

また,

$fi$

の双対関数

,

記の

$f_{1^{d}}$

$f$

は,

がランク
ランク

$r$

[10] 参照.

。

$a\in\iota \mathfrak{n}inT(f_{K})$min$\neq\phi$

に

であ

に対して,

が存在する.

であるような証明

K- スタイナー木にいくらかの枝を加え, 全域$a’\in$$T(f_{V})$$iT(f))$$,x\geq^{*}a$

対し て$L^{arrow}a_{1_{\beta^{\llcorner}}}\in$のとき木をっくることができることより, 明らか.

{のマトロイ ド関数ならば,

上$n-r$ のマトロイ ド関数になる.
口$\prime n_{3}\leq m_{1}(n-r)$

口

補題 4.3 グラフ $G=(V, E)$ とターゲット集合
対する, K- スタイナー木関数$x\in$

min$f_{K}$$T(f_{V})$, 全域木関数に対して,$It^{-}$$f_{V}$$a\leq x$ににであるような $a\in lninT(f_{K})$ がただ一っ存在する.

系 4.1 $m_{3}=| \min T(fi)|,$ $m_{1}=| \max F(fi)|$ とす
るとき,

すべての

$S$

$f_{V}$$a’\geq a$

おいて, 任意の証明, 全域木関数

おいて, 各 $a\in$ nln $T(f_{K})$ に対して,る. すなわち,は次のように与えられる.

あそのる$f_{1}^{d}(x)=\{01$

補題 41$f_{1}^{d}$$f_{K}$

が成立する.

証明

全域木とその部分グラフである K- スタイナ $-$木の関係より. 明らか.

口

233
系 4.2 グラフ $G=(V, E)$ とターゲット集合 $K$ に
対する,

K- スタイナー木関数

おいて,$a^{(1)},$ $a^{(2)},$$f_{K}$$a^{(m)}\in$$\ldots,$, 全域木関数$f_{V}$

より,$||\alpha||=|V|-1$ である.

$||\beta-a^{(1)}||$

min $T(f_{K})$ とすると

き. min $T(f_{V})$ は互いに素なベク トル集合によって

一意に

より,

口

$\leq$$2+|(|V|-1)-(|K|-1)|$$=$$|V|-|K|+2$$\beta$が未知ベク トルであることに矛ある$f_{V}$

補題 4.4 グラフ $G=(V)E)$ とターゲット集合 $K$ にする.

対する, K- スタイナー木関数$x\in T\cup F$ である.

$f_{V}$に$T(f_{V})\subseteq T(f_{\Lambda}\cdot)$$x\in T$ が得られると, ある $\beta’\in S_{b}$ において,とすると,$|I_{\beta’}-I_{\alpha’}|<k$(1) 全域木は K- スタイナー木でもあることかして$a^{(1)}$ら, 明らか. (2) $(maxF(fv))$ は極小カッ トの集合,

ル列$a^{(1)},$ $a^{(2)},$mqax$F(fJ_{1’}))^{*}$

え,

より,

明らか.

口

二っの集合 $X,$

$Y$$|x\in X,$ $y\in Y$} という記法を用いる.

$($$x\in T(f_{V})$は $K$ を分ける極小カットの集合を表す$b\in$

において $||X-Y||= \min\{||x-y||$対する, K- スタイナー木関数となる.

$\cdots,$$a^{(t)}=b$

は $MT$ に属する.

それゆ

mln $T(f_{K})-MT$ であることに矛盾する.

口$f_{K}$

かっ, 各 $a\in MT$ に対して $||x-a||\leq$$x$が $T\cup F$ に含まれ$\alpha\in s_{\text{。}}(1)$と,$S_{b}-S_{\text{。}(1)}||=||\beta-\alpha||,$$f_{V}$, 補題 42 より,, かっ, 系 4.2 より,

$g$

にお

$x$

が $T\cup F$ に含まれるならば, M $F=lnaxF(K)$ である.

任意の $b\in maxF(f_{K})$ を考える. グラフ $G=$

証明$(V, E)$ の全域木関数を $fv$

り,導く. グラフ $G=(V, E)$ の全域木関数を$a^{(1)}\in MT$ を一っ選ぶと

の部分関数

$g$

$b \in\min T(f_{K})-MT$ が存在するとして矛盾をあるに対と同様な操作を繰り返して得られるベク ト

対する, K- スタイナー木関数とする.

$S_{\text{。^{}(1)}}\neq\phi$$S_{b}\subseteq U$$S_{\text{。}}(1)\subseteq T,$

ある $\beta\in S_{b}$ において,$k=|I_{\beta}-I_{\alpha}|$し, $k=1$ ならば,$||\beta-\alpha||=2$

スタイナー木より,$||a^{(1)}||\geq|K|-1,$

となる.

,

とする.
$a^{(1)}$$\alpha$max$b\in$意のである.

$a^{(2)}$いて, 任意の $a\in MT\cup MF$ に対して, $||x-a||\leq$

るならば, $MT=1ninT(f_{K})$ である.

$S_{b}\neq\phi$

さらに,の部分関数 におい

$f_{ic}$$|V|-|K|+2$ をみたすすべての証明$\alpha’\in S_{a(2)}$$||S_{b}-S_{\text{。^{}(2)}}||=||\beta’-\alpha’||$$|V|-|K|+2$ をみたすすべての$MT\neq\phi$. 補題 4.3 より,

補題 4.6 グラフ $G=(V, E)$ とターゲッ ト集合 $K$ に

補題 4.5 グラフ $G=(V, E)$ とターゲット集合 $K$ にて,より, 補題存在する. 従って, $a^{(2)}\in MT$ であり, ある(2) $\max F(fic)\subseteq\max F(f_{V})$
証明

さらに,

であるような $a^{(2)}\in$ min $T(f_{K})$ がただーっ$a^{(2)}\leq x$(1)

mln $T(f_{V})$ が存在

そのとき, $||a^{(1)}-x||\leq|V|-|K|+2$ より,$4.4(1)$ を用いて,おいて, 次の 2 つの条件を満足する.

はマトロイ ド関数と $j\in I_{\beta}$ –I。に対して,$i\in I_{\alpha}-I_{\beta}$$x=\alpha-e_{i}+e_{3}$ であるような $x\in$, 全域木関数より,$||\beta-\alpha||+||\alpha-a^{(1)}||$

盾するので, $k>1$ である.

$f_{K}$$a_{(1)}\not\leq\beta$$=$となる. 従って,$\min T(f_{V})=\bigcup_{j=1}^{m}S_{a(j)}$と分解される.

また,

に

$j$

$\in$

$Z_{b}$$F(f_{V})$より,$a-e_{j}\leq$$b$であるようなが存在する. 補題 4.4 (1), 補題 45$a\in T$ であり,が存在する.

である. 補題 3.3 (2) より, {壬に対して,$a\in 1ni_{1}\iota T(f_{V})$とすると, 補題 44(2) よ$a’\leq \mathfrak{a}$であるような $a’\in MT$$a-e_{j}\in F$ より,$a\not\leq a-e_{J}$

である.

従って,

$||$

も

は K-

は全域木

1 $(a-e_{j})-a’$ I$=$$||(a-e_{J})-a||+||a-a’||$$\leq$$1+|(|V|-1)-(|K|-1)|$$=$$|V|-|K|+1$

234
より,

$b\geq a-e_{3}$ であるような$c\in MF$ が存在す

補題 34, 補題 4.4 より, $c=b$ である. つまり,

る.

$b\in MF$ である.

口

$h,$

$36,$

$P1$ )$.703- 715$

(1988),[4] Boros E., lIammer P.L., Ibaraki T. and
Kawakami K. :($Identifyi\iota\iota g$

2-moitotonic pos-の節点集合

itive Boolean functions in polynomial time’)に対する K- スタイナー木関数のクラスを $S(l, k)$Proc. 2nd International Symposium on Algo-は,rithms, Lec ure Notes in Computer Science

定理 42 節点数 をもっグラフの位数
$l$

$K$

Operations Researcとするとき,

このクラスの最大潜伏度$k$$\Lambda_{S(\mathfrak{l},k)}(n)$557, Springer-Verlag, pp. 104-115 (1991).

$\Lambda_{S(l,k)}(n)\leq l-k+2$ をみたす.

補題 45, 補題 46 より明らか.

証明

$t$

[5] Colbourn C.J. :口($T1\iota e$

combinatorics of et$\iota\iota$

work reliability“, Oxford University Press

5(1987).

むすび
本研究では, 論理関数を正関数に限定し, 不完全定義関数における未知ベクトルの発見の尺度として,最大潜伏度$\Lambda_{C}(n)$の概念を導入した. マトロイ ド関

数のクラス $M$ において, 最大潜伏度 $\Lambda_{M}(n)=2$ であること,

K- スタイナー木関数のクラス $S(l, k)$ における最大潜伏度の上界値 $l-k+2$ を与えた.

た,

Cause-effect relationships and patially defined
Boolean functions”, Annals of Operattons Re-

searc

$h,$

$16$

, pp.299-326 (1988).

[7] Gainanov D.N. :$t$((

On one criterion ofhe optimality of an algorith$m$for evaluat-

ing monotonic Boolean functions”, U. S. S. .

その同定が多項式時間で可能である. まComputational Mathematics and Mathemati-

マトロイ ド関数の双対関数を求める問題も,多項式時間で可能である.
謝辞$($

最大潜伏度が定数とマトロイ ド関数においては,なるため,[6] Crama Y., Hammer P.L. and Ibaraki T. :よび, 文献 [3] を示し, 貴重なコメントをいただい
なお, 本

研究は一部文部省科学研究費によるものである.

理関数の潜伏度にっいて”, 信学技法 COM P92-

3, pp.19-25,(1992).

[9] Muroga S. : “Tbreshold Logic and Its Appli$cati_{onS}))$

Wiley-Interscience (1971).

[10] Papadimitriou C.1I. and

参考文献[1] Angluin D. :cal Physics, 24, pp.176-181 (1984).

[8] 牧野和久, 茨木俊秀 :‘(不完全に定義された正論

日頃御議論いただいている研究室の皆様, おた Y. Crama 教授に深謝の意を表します.

$R$

$S$

teiglitz\langle . : ((Com-$I$

binatrial optimization: Algori thms and Com-

“Learning regular sets from

queries and counter -examples“, Information
and Computation, 75, pp.87-106 (1987).
[2] Angluin D. : “Queries and concept learning”,

Machine Learning, 2, pp.319-342 (1988).
[3] Ball M.O.,and Provan J.S. : ”Disjoint products and efficient computation of reliability“,

plexity“, PRENTICE-IIALL (1982).

[11] Peled U.N. alld Simeone B. : “An $O(nm)$ -timealgorithm for computing$tl\iota e$dual of a regular

Boolean function“, Technical Report, Univer-sity Illinois at Chicago (1990).
[12] Sokolov N.A. : “On the optimal evaluationof monotonic Boolean functions“, U. S. S.

$R$

.

235
Computattonal Mathematics and Mathemati$cal$

Physics, 22, pp.207-220 (1979).

[13] Valian L.G. :$t$(Atheory of the learnable’)Commun. A CM, 27, pp. 1134-1142 (1984).