修正ペブルゲームとは「値が0のペブルがひとつだけとなったペブル状態では、値が0のペブ ルと他のペブルの比較を行わない」という制約を追加したペブルゲームである（定義2.15）。この 修正ペブルゲームの制約を満たしてペブル状態0122. . .22以上の状態にする、次の修正ペブルプ レイ戦略5.16が存在する。
ペブルプレイ戦略5.16 1. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さいペブ ルの値が2以上なら、比較を終了する。
2. そうでなく、値が2番目に小さいペブルの値が1以上ならば、下記の比較を同じ深さで行い 次の深さへ進む。
(a) 1同士の比較を可能な限り多く行う。
3. そうでないなら下記の比較を同じ深さで行い、次の深さへ進む。
(a) 0同士の比較を可能な限り多く行う。
(b) 上記の比較で0が余り、1が1個以上あるなら、0と1の比較を1回行う。
(c) 上記の比較に用いない1同士の比較を可能な限り多く行う。
0と0 0と0 0と0 を比較
0と0 0と0 1と1 を比較
0と0 1と1 1と1 を比較
1と1 を比較
1と1 を比較
初期状態 目標状態以上
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 1 1 1 1 2
0 1 1 1 2 2 2
0 1 1 2 2 2 2
0 1 2 2 2 2 2 図23: 目標状態が0122222の修正ペブルプレイ戦略5.16の例
この修正ペブルプレイ戦略は、値が0のペブルを含む任意の状態から、0122. . .22以上の状態 にする、最小深さの修正ペブルプレイ戦略である。
補題5.17 ペブルプレイ戦略5.16は、値が0のペブルを含む任意のペブル状態から、ペブル状態
0122. . .2以上の状態にする最小深さペブルプレイ戦略である。
補題5.17を証明するために、よく似た2つのペブル状態から目的状態0122. . .2までの最小深 さを比べる次の補題5.18を証明した。
補題5.18 a, bを任意のa≤bを満たす自然数、Pを任意のペブル状態とする。
a−1→aが 1回多い
b→b+ 1が 1回多い P0
a−1 b
目的状態 必要深さ
少ない
多い P
a b
P a−1 b+ 1
0122. . .2
図24: 補題5.18のイメージ図
この時、ペブル状態P+a+bとP+ (a−1) + (b+ 1)がどちらも値が0のペブルを含んでいる 状態ならば、次の式が成り立つ。
DF(P +a+b,0122. . .2)≤DF(P+ (a−1) + (b+ 1),0122. . .2) (48)
最小深さ修正ペブルプレイ戦略5.16をプレイした時の深さを数えることにより、補題5.17の系 として、いくつかの状態から0122. . .2以上の状態までの修正ペブルプレイ戦略の最小深さが得 られた。（証明略）
系5.19 kを十分に大きい任意の自然数とする。
この時、次の式が成り立つ。
D(0 + 1,0122. . .2) = 0 (49)
D(0 + 1·k,0122. . .2) = 1 +D (
0 + 1·
⌈k 2
⌉
,0122. . .2 )
(50)
=⌈log2k⌉ (51)
D(0·2k,0122. . .2) =k+D(0 + 1·k,0122. . .2) (52)
=k+⌈log2k⌉ (53)
ペブルゲームの最小深さは入力数に比例するため、系5.19より補題5.17の系として、任意の 数の値が0のペブルのみからなる状態から、0122. . .2以上の状態までの修正ペブルプレイ戦略の 最小深さの下界と上界が得られた。（証明略）
系5.20 nを任意の自然数とする。
この時、n個の値が0のペブルのみからなる状態から0122. . .2以上の状態までの修正ペブルプ レイ戦略の最小深さについて、次の式が成り立つ。
⌊log2n⌋+⌈log2⌊log2n⌋⌉ ≤D(0·n,0122. . .2)≤ ⌈log2n⌉+⌈log2⌈log2n⌉⌉ (54)
6 証明の方針
本セクションでは、本研究で導かれた各命題をどのように証明するのか、その方針を示す。V 型2セレクションネットワーク・U型セレクションネットワーク・V 型4セレクションネットワー クの最小深さおよび、それぞれに対応するペブルゲームの最小深さペブルプレイ戦略の証明の方 針は、同じ構成になっている。そのため本セクションでは、V 型2セレクションネットワークに 対しての命題を例にとって説明を行う。
6.1 セレクションネットワークの最小深さに関する結果の証明の方針
本サブセクションの目的は、セレクションネットワークの最小深さのタイトな下界を求め、可 能ならば最小深さを決定することである。セレクションネットワークの最小深さのタイトな下界 を得るために、セレクションネットワーク上でペブルゲーム解析を行ったときのペブル状態の必 要条件を調べ、セレクションネットワークの最小深さはそのペブル状態にするための最小深さペ ブルプレイ戦略の深さ以上であること（補題4.1）を示す。さらにタイトな下界を得るために、セ レクションネットワークの最小深さはそのペブル状態にするための最小深さ修正ペブルプレイ戦 略の深さ以上であること（補題4.4）を示す。可能ならば最小深さを決定するために、最小深さペ ブルプレイ戦略の深さが計算しやすい入力数に着目し、その入力数でのセレクションネットワー クの最小深さの上界との差（補題4.5）を示す。
命題 4.1(抜粋) nを任意の自然数とする。
n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0·nとして ペブルプレイ戦略5.1をプレイした時の深さ以上である。
V 型2セレクション ネットワークの
出力の最小値 min 1
min 2
min 3 min 3
min 3
ペブルゲームの 出力の最小値
⌈log21⌉= 0
⌈log22⌉= 1
⌈log23⌉= 2
⌈log23⌉= 2
⌈log23⌉= 2 図25: V 型2セレクションネットワークとペブルゲーム解析の関係
Alekseevの先行研究[1]の補題3.1により、V 型2セレクションネットワーク上でペブルゲーム 解析を行った時の出力は0,1,2,2, . . . ,2となることが得られる（図25）。「ペブルゲームの最小深
さに関する結果」の補題5.2よりペブルプレイ戦略5.1は0122. . .2以上の状態になる最小深さペ ブルプレイ戦略であるため、補題4.1は示される。
命題 4.4(抜粋) nを任意の自然数とする。
この時、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0·n として修正ペブルプレイ戦略5.16をプレイした時の深さ以上である。
Alekseevの先行研究[1]の補題3.1により、V 型2セレクションネットワーク上でペブルゲーム 解析を行った時に値が0のペブルはmin 1候補に対応していることがわかる。値が0のペブルが 1つだけの深さではmin 1が確定しており、min 1とmin 2をセレクションするためには既に確定
したmin 1を他の値と比較する必要がないことから、値が0のペブルが1つだけの深さではその
ペブルを他のペブルと比較しない戦略、すなわち修正ペブルプレイ戦略が最小深さV 型2セレク ションネットワーク上でペブルゲーム解析を行ったときの戦略となる。「ペブルゲームの最小深さ に関する結果」の補題5.17より修正ペブルプレイ戦略5.16は0122. . .2以上の状態になる最小深 さ修正ペブルプレイ戦略であるため、補題4.4は示される。
命題 4.5(抜粋) kを任意の自然数とする。この時、2k入力V 型2セレクションネットワークの 最小深さについて、次の式が成り立つ。
V Depth(2,2k) =k+⌈log2k⌉ (55)
0と0 0と0 0と0 0と0 を比較
0と0 0と0 1と1 1と1 を比較
0と0 1と1 1と1 を比較
1と1 を比較
1と1 を比較
初期状態 目標状態以上
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 2 2
0 1 1 1 2 2 2 2
0 1 1 2 2 2 2 2
0 1 2 2 2 2 2 2
図26: 目標状態が01222222の最小深さ修正ペブルプレイ戦略5.16の例
2k入力V 型2セレクションネットワークの最小深さの下界については、ペブルプレイ戦略5.16 の各深さでのペブル状態を追っていくことで求まる。値が0のペブルの数（以降は0の数）が2 以上の深さでは、深さが1増える度に0,1の数が半分になり、減った0の数だけ1の数が増加す る。0の数が1になってからは、深さが1増える度に1の数が半分（端数切り上げ）になる。これ により、補題4.5の下界が求まる。
2k入力V 型2セレクションネットワークの最小深さの上界についても、下界の時と同じように 2セレクションネットワークの各深さでのmin 1候補と非min 1候補だがmin 2候補の数を追って いくことで求まる。各深さでmin 1候補同士の比較とmin 2候補同士の比較のみを可能な限り行
出力の最小値 min 1
min 2
min 3 min 3 min 3 min 3 min 3 min 3 図27: 8入力V 型2セレクションネットワークの例
うセレクションネットワークを考えた場合、min 1候補の数が2以上の深さでは、深さが1増える 度にmin 1候補・min 2候補の数が半分になり、減ったmin 1候補の数だけmin 2候補の数が増加 する。min 1候補の数が1になってからは、深さが1増える度にmin 2候補の数が半分（端数切り 上げ）になる。これにより、補題4.5の上界が求まる。