Minesweeper の解を唯一にするための計算量関口愛生

1(指導教員：長尾篤樹)を決定する問題であり、Σ2 P 困難であることが [2] で証明されている。まず、UQSAT のインスタンスを論理回路に書き換え、それを基にガジェットを組み立てることで帰着先である問題のインスタンスを作る。

はじめに理論計算機科学分野における組合せゲーム理論では、多くのゲームやパズルの計算量の解析が行われている。本研究では Minesweeper というコンピュータゲームに関連した問題について取り上げ，Minesweeperの解を唯一にする問題の解析を行う．先行研究ではMinesweeper と類似した NP 完全であるパズルゲームの解を唯一にするための計算量の解析が行われており、
Σ2 P 完全であることが証明されている。以上の証明を参考に、唯一解を求めることを目的とした Minesweeperの決定性問題を定義し、Σ2 P 完全であることを示す。

2

本章では MCP の FCP バージョンを決定性問題として定義し、それが Σ2 P 完全であることを証明する。

Deﬁnition 2. FCP Minesweeper Consistency Problem(以下 FCP MCP とする) は以下の入力に対し、以下の質問を解く問題である。
入力：Minesweeper の盤面 B, 整数 k
質問：B の中の未確定である k マスに新たに爆弾を配置することで、残りの盤面に整合性を保ったまま爆弾を一意配置できるか？

Minesweeper Consistency Problem

Minesweeper Consistency Problem は 与 え ら れ た
Minesweeper の盤面に矛盾なく爆弾を配置することが で き る か ど う か を 問 う 、Kaye に よ っ て 定 義 さ れた Minesweeper の決定性問題である。以下の定理をKaye[1] が証明した。
Theorem 1. [1] Minesweeper Consistency Problem
は NP 完全である。
先行研究で Kaye が Minesweeper Consistency Problem(以下、MCP とする) の NP 困難性を circuit SATからの帰着で証明した。circuit SAT の入力を基に [1]にある各ガジェットを組み立てることで MCP のイン

本節では上で紹介した [1] と [2] の証明を参考に、以下の定理を証明する。
Theorem 3. FCP MCP は Σ2 P 完全である。

Proof. まず Σ2 P 困難あることを証明する。[1] にある MCP の NP 完全性を示した帰着と同様の帰着をX !
1 1 2 1 1X !
NP· · ·完全と知られる
SAT から行うことで、
1 1 1 1 1 2 ⇤ 3 ⇤ 2 1 1 1 circuit
1 1 ······x x 1 x x 3 x 5 x 3 x x 1 x x ···MCPの盤面を構成することができる。これを利用し··· 1 1 1 1 1 2 ⇤ 3 ⇤ 2 1 1 1 1 1 ···1 1 2 1 1て、UQSAT のインスタンス ϕ(X, Y ) から量化記号を考慮しない MCP の盤面 Bϕ を構成する。Bϕ に [2] がFigure 7: A phase-changer made from two not gates.
FCP Akari の Σ2 P 完全性を示す際に利用した Assign0

FCP バージョンの問題

前章で紹介した Minesweeper を含め、パズルでは解が唯一であることを求められる場面がある。解を唯一にするために、Demaine ら [2] は FCP という枠組みを定義した。FCP とは Fewest Clues Problem の略称であり、k を整数として、最大 k 個の手がかりによって解を一意に定めることができるかを問う問題である [2]。
これにより、多くの NP 完全と知られる問題の FCPバージョンは Σ2 P 完全であることが示されている。ここで、Σ2 P とは NP オラクルを持つ非決定性チューリ
ングマシンによって決定される言語が属する複雑性クラスであり、NP オラクルとは NP に属する問題を 1ステップで解くことができるブラックボックスである。

3.1

Σ2 P 完全性

4.1

スタンスを構成する。

3MCP の FCP バージョン

40000

ガジェットを追加することが本証明の流れとなる。
本証明では assign ガジェットとして XOR ガジェッ
ト [1] を用いる。その構成を以下の図に示す。
：terminalガジェットU !
1 1 1 1 1 1
1 1 1 W !
1 1 1 1 2 ⇤ 3 3 ⇤ 2 1 2 ⇤ 2 1 1 1u0 u 1 u0 u 3 ⇤ ⇤ 3 w w 0 3 w 3 w 0 w 1
1 1 1 1 1 2 u0 w 0 2 1 1 2 ⇤ 2 1 1 11 2 3 3 2 2 2 3 2 1
1 1 1 1 3 ⇤ u w ⇤ 3 ⇤ ⇤ 2 1v 0 v 1 v 0 v ⇤ v 0 6 x 4 x0 6 ⇤ 21 1 1 1 2 3 ⇤ x ⇤ 3 ⇤ x ⇤ 2V !
2 3 5 3 3 2 x0 2 1
1 ⇤ x0 ⇤ 1 1 1 1
2 3 4 2 2 2 x 12 ⇤ x 1 2 ⇤ x0 2 12 ⇤ 5 x0 4 x 5 ⇤ 11 2 ⇤ ⇤ 3 ⇤ ⇤ 2 1
1 2 2 2 2 2 1

MCP に近い FCP バージョンに関する既存研究：XORガジェット：wireガジェット：他の盤⾯!

"

上述の通り、一部の NP 完全である問題の FCP バージョンは Σ2 P 完全であることが証明されている。[2]では上記のような問題とその証明が紹介されており、その一つに FCP Akari がある。一方で、Akari の NP 完
全性は [3] が circuit SAT からの帰着を利用して証明していることから、本研究では Minesweeper の FCPバージョンが Σ2 P 完全であることを示すために、FCPAkari の帰着を踏襲した証明を行う。具体的には、Σ2 P困難であることを証明するために、UQSAT からの帰着を行う。UQSAT は論理式 ϕ(X, Y ) を入力として受け取ったときに Y 中の変数への唯一の割り当てが存在するような X 中の変数への割り当てが存在するかどうか

Figure8: An xor gate.
XORガジェット

整合性を保って爆弾を配置できるとき、$ = "⨁#が成⽴する。

!
#(" = $⨁&)

図 1 XOR 6ガジェット [1] とガジェットの置き換え

図 1 左において、u で示されるマスのうちいずれか一つに爆弾があると仮定する。この場合、整合性が取れる
ように爆弾の配置を考えると全ての u で示されるマスに爆弾が置かれ、全ての u′ で示されるマスにはいずれかの数字が置かれる。また、u, v で示されるマスに爆弾があると仮定すると、w で示されるマスにはいずれかの数字が置かれ、u, v いずれか 1 つに爆弾が置かれる

12と w に爆弾が置かれる。このガジェットを UQSAT のX に含まれる変数に相当するガジェットに追加することで FCP MCP のインスタンス Bϕ′ を構成できる。
以下、XOR ガジェットが Assign ガジェットのはたらきをすることを確認する。変数 u, v を導入し、x = u⊕vとする。このとき、(u, v) = (1, 0) または (0, 1) とすることで x = 1、また、(u, v) = (0, 0) または (1, 1) とすることで x = 0 と x のへの割り当てを定めることができる。同様に、u, x の組、v, x の組についても割り当てを固定することで v, u の値を定めることができる。したがって、任意の 2 変数への割り当てを定めることで選択しなかった 1 変数への割り当てを一意に定めることができる。この事実を利用し、Bϕ の X に含まれる変数に相当する terminal ガジェット全てを XOR ガジェッ
トで置き換えることで、それぞれにつき 2 個の手がかりで 3 つの変数への割り当てを 1 通りに定め、Bϕ′ を充足する割り当てを唯一にすることができる。
ϕ が充足不可能なときに、同様の変更を terminal ガジェットに行っても、Bϕ′ を充足する割り当てが存在しないことは容易に確認できる。また、このように盤面を構成する場合、X に含まれる変数に対応する XOR ガジェットに対して、変数マスに対する 1 つの手がかり
では Bϕ′ 全体への配置を唯一に決定することができないことから、必ず 2 つの手がかりが必要と言える。
以上より、ϕ の量化記号の変数が k 個であるとき、Bϕ′は 2k 個の手がかりによって解を唯一に定めることができる。
逆に、FCP MCP の盤面 Bϕ′ の未確定である 2k マスに爆弾を配置することで Bϕ′ の残りの未確定マスに整合性を保ったまま爆弾を一意に配置できるときに、ϕ が充足可能であることを示す。上述の帰着では、ϕ を元に構成した FCP MCP の盤面 Bϕ′ は Assign ガジェットを k = |X| 個持つ。
Bϕ′ に新たに配置する爆弾は X に含まれる変数または Y に含まれる変数に影響を与える。ここで、一つ以下の新たに配置する爆弾にしか影響を受けていない変数 x∗ ∈ X が存在すると仮定する。Assign ガジェットの構成法より、x∗ の割り当ては一意に定まらないことになり、前提に矛盾した配置と言える。よって、X に含まれる全ての変数は 2 つ以上の新たに配置した爆弾に影響を受けていることがわかる。配置する爆弾の個数
は 2|X| 個なので, X に含まれる全ての変数はちょうど2 つの新たに配置した爆弾に影響を受けており、Y に含まれる全ての変数は新たに配置する爆弾の影響を受けていないことが言える。これにより、新たに配置した爆弾を持つ Bϕ′ は残りの未確定マスに整合性を保ったまま爆弾を一意に配置できる。さらに、X に含まれる全ての変数に対し、新たに配置した爆弾に相当する割り当てを固定することで、ϕ(X, Y ) の X を割り当てた後の論理式は残りの未確定マスに整合性を保ったまま爆弾を一意に配置する方法に相当した充足解を唯一に持つ。
よって、ϕ(X, Y ) に対し、充足解が 1 通りになるようなX の割り当てが存在する。
次に、FCP MCP が Σ2 P に属することを示す。そのために、次に示す MCP オラクルを持つ非決定性チューリングマシン M が FCP MCP を判定することを示す。

1! "

#

110001110100!
#"(# = !⨁")

x = u ⊕ v により、1 の部分の未確定マスが定まり、2 で示す全体に対し割り当てが一意に決まる。

図2する。

2 残りの盤面に整合性を保ったまま爆弾を配置する
方法が 1 通り以上存在するかどうかを MCP オラクルで判定する。存在しなければ拒否する。

3 整合性を保ったまま爆弾を配置する方法が 2 通り以上存在するか否かをオラクルで判定する。存在するならば拒否し、存在しなければ受理する。
上記の M は明らかに線形時間で受理または拒否をし、停止する。受理をする際は、k 個の爆弾を新たに配置することで唯一解にすることができるインスタンスが入力であることが確認でき、拒否する際は、k 個の爆弾を配置しても唯一解にすることができないことが確認できる。さらに用いている MCP オラクルは NP に含まれる MCP を判定するオラクルである。以上より、Mは NP オラクルを持ち、多項式時間で挙動をする非決定性チューリングマシンであり、FCP MCP を正しく判定するため、FCP MCP は Σ2 P に属す。

5

まとめと今後の課題

本研究では UQSAT からの帰着により FCP MCP のΣ2 P 完全性を証明した。
Assign ガジェットとして利用した XOR ガジェットに着目し、UQSAT からの帰着をより多くの FCP バージョンの問題に対して構成できないかが考えられる。
SAT からの解を一対一に保存した帰着が存在する場合には、この構成を利用して FCP バージョンが Σ2 P であることが容易に証明できることが期待される。それ以外の場合についても NP 完全である問題の FCP バージョンが Σ2 P 完全になるための必要十分条件についても検討が必要である。

参考文献[1] Richard Kaye. Some minesweeper conﬁgurations, 2000. https://web.mat.bham.ac.uk/R.
W.Kaye/minesw/.
[2] Erik D Demaine, Fermi Ma, Ariel Schvartzman,
Erik Waingarten, and Scott Aaronson. The fewest
clues problem. Theoretical Computer Science,Vol. 748, pp. 28–39, 2018.
[3] Brandon McPhail. Light up is np-complete. Unpublished manuscript, 2005.

1 非決定的に未確定のマスを k 個選び、爆弾を配置
2