NP 完全性の証明

ここまでで定義, 証明した事項を基に, PICROSS-3D (高さ1)のNP完全性を証明する. φ が充足すると仮定する.

(i) 1節目

φ が充足するような各リテラルの値を, 1 回目の真偽値対応部分に割り当てる.補題2よ り, 2回目以降に使用される真偽値対応部分の値も, 1回目のものと同じになる.Tの構成法か

3.3 高さ1でセグメント数を指定する立体ピクロス

上に現れる 1 の数は, 高々2 つとなる. 現れた 1 の数を n とすると, p1,1,capsumZ(m)+2, p3,1,capsumZ(m)+2に(2−n)個の1を割り当てることで, ヒントを満たすことができる.

(ii) k 節目以降(2≦k) k節目以降では, 判定に使用するリテラルの使用回数にずれが生 じるが, 補題2により常に各リテラルの値は同じである. φ は充足するため, 使用するリテ ラルの真偽値対応部分と同じX 座標のz = capsumZ(m) + 2k 上に現れる1の数は, 高々 2つとなる.現れた1の数をnとすると,p1,1,capsumZ(m)+2k, p3,1,capsumZ(m)+2k に(2−n) 個の1を割り当てることで, ヒントを満たすことができる.以上より, φ が充足するとき, 立 体ピクロスは解を持つ.

立体ピクロスが解を持つと仮定する. (i) 1≦z≦capsumZ(m) + 2の場合

φ に よって 構 成 さ れ た 立 体 ピ ク ロ ス に 解 が 存 在 す る 場 合, T の 構 成 法 か ら, p1,1,capsumZ(m)+2, p3,1,capsumZ(m)+2 以 外 の z = capsumZ(m) + 2 上 に 現 れ る 1 の 数が, 高々2つになるような各リテラルの1回目の真偽値対応部分への0, 1の割り当ての集 合Rが存在する.この割り当てにおいて, φ の 1節目は少なくとも1つの真のリテラルを 含む.

(ii) capsumZ(m) + 2＜z ≦dの場合

補 題 2 に よ り, (i) に お け る 割 り 当 て が 2 回 目 以 降 も 保 持 さ れ る が, 立 体 ピ ク ロ ス に は解が存在するため, j 節目 (j = 2,3, .., k) の判定を行う z = capsumZ(m) + 2j で, p1,1,capsumZ(m)+2, p3,1,capsumZ(m)+2以外の部分に現れる1の数を, 全てのj で高々2つに できるようなリテラルの割り当てが集合Rの中に少なくとも1つ存在する.この割り当てに おいて, φのj 節目は少なくとも1つの真のリテラルを含み, (i) と合わせて φ 全体を充足 させる割り当てとなる.よって, 立体ピクロスに解が存在するとき, φ を充足させるリテラル の割り当てが存在する.

以上より, 次の定理が導ける.

定理 3.3.1. PICROSS-3D (高さ1)はNP完全である.

第 4 _章

まとめ

4.1 結論

本研究では, セグメント情報のない立体ピクロス, 及び高さ1でセグメント数の指定をす る立体ピクロスの解の存在判定問題が NP完全であることを証明した.先行研究[3]の結果 と合わせると, 立体ピクロスはセグメント情報の指定, 高さが自由であることのどちらもが NP完全に寄与しており, この条件のどちらか片方に当てはまれば解の存在判定がNP完全 になることが明らかになった.

4.2 今後の課題

先行研究[3]では, セグメント情報のある立体ピクロスは高さを4に限ってもNP完全で あることを証明している.本研究で証明したセグメント情報のない立体ピクロスのNP完全 性は, 高さ自由という条件で証明されたため, 高さを定数以下に限定した場合NP完全であ るかどうかはまだ分かっていない.定数以下の高さでのセグメント情報のない立体ピクロス の計算複雑さには, まだ研究の余地が残っていると言える.

謝辞

本研究を進めるにあたり, 多大なる御助言, 御指導を頂きました指導教員の高田 喜朗准教 授に, この場を借りて厚く御礼申し上げます.

また, 副査を務めて頂きました松崎 公紀准教授, 鵜川 始陽准教授に深く感謝致します. 最後に, 日頃から御協力, 御支援頂いたソフトウェア検証・解析学研究室の皆様に感謝し ます.