立体ピクロスの計算量解析
概要
立体ピクロスは任天堂が2009年に発売したゲームです[1]。 我々は計算機が立体ピクロスを解くことがどのくらい難しいかを解析し、 立体ピクロスの解の存在判定がNP完全である（立体ピクロスを解くことはとても難しい）ことを証明しました[2]。
通常のピクロスの解の存在判定や[3]、 サイズを一般化しNEXTぷよが全て見えている「ぷよぷよ」で全消しが可能か判定する問題[4]などがNP完全である（立体ピクロスと同程度に難しい）ことが知られています。
立体ピクロスの問題と解
NP完全
「与えられた配列を昇順に並べ替える」「迷路の最短経路を探す」「画像に書かれている文字を読み取る」など計算機が解く種々の問題があります。 このうち答えが「はい」か「いいえ」であるものを判定問題と言います。 「与えられた立体ピクロスを解け」は判定問題ではありませんが、「与えられた立体ピクロスは解を持つか？」は判定問題です。
判定問題「与えられたグラフが一筆書きできるか？」を考えます。 この問題の答えは、繋がっている辺の数（次数）が奇数である頂点の個数が2個以下であれば「はい」、そうでなければ「いいえ」ということが知られています。 グラフの頂点数をnとすると、ある頂点の次数は高々n-1なので、全ての頂点の次数を調べると、O(n2)（n2の定数倍）の時間で解くことができます。 この問題のように問題サイズnの定数乗の時間（多項式時間）で解ける問題をP（Polynomial timeの略）と言います。
「n桁の正数xは合成数か？」という問題を考えます。 xが合成数であるならば、x=pq (p,q>1)のpとqを教えてもらえば、 pqのかけ算はO(n2)で計算でき、xが合成数であることが確認できます。 この問題のように「はい」となる証拠が与えられれば多項式時間で解ける問題をNP（Non-deterministic Polynomial timeの略）と言います。 実際にはこの問題はPでもある（証拠が無くても多項式時間で解ける）ことが最近証明されました[5]。
NPの中で多項式時間の差は除いて最も難しい問題をNP完全問題と言います。 NP完全問題はNPの中で最も難しい問題なので、NP完全問題がPならば全てのNPに属する問題はPに属します。 NP≠PなのかNP＝Pなのかというのは非常に重要かつ難しい問題で、100万ドルの懸賞金がかけられています。
立体ピクロスの解の存在判定はNP完全
我々は立体ピクロスの解の存在判定がNP完全であることを証明しました。 立体ピクロスの解の存在判定がNPであることは、すぐに分かります。 解の存在判定が全てのNPに属する問題よりも（多項式時間の差は除いて）難しいことを示す必要がありました。 3-SATという問題は既にNP完全であることが知られています。 我々は、立体ピクロスが多項式時間で解けるならば、3-SATも多項式時間で解けると証明しました。 このことから、もし3-SATが多項式時間で解けないのならば、立体ピクロスも多項式時間では解けないことが分かります。 具体的には、任意の3-SATの問題に対して、3-SATの問題と答え（「はい」or「いいえ」）が一致するような立体ピクロスの問題の構成法を示しました。 これは、3-SATから立体ピクロスの解の存在判定への帰着と言い、NP完全の証明に一般に用いられる手法です。
実は
実は、ゲームの立体ピクロスの中には、そんなに難しい問題は収録されていないそうです。
参考文献
- 任天堂株式会社.
立体ピクロス,
http://www.nintendo.co.jp/ds/c6pj/, 2011/5/20閲覧. - 草野 一彦, 成澤 和志, 篠原 歩.
立体ピクロスはNP完全,
第15回ゲームプログラミングワークショップ(GPW-10), pp. 108-113, 2010年11月. - Nobuhisa Ueda, Tadaaki Nagao.
NP-completeness Results for NONOGRAM via Parsimonious Reductions,
Technical Report TR96-0008, Tokyo Institute of Technology, 1996. - 牟田 秀俊.
ぷよぷよはNP完全,
電子情報通信学会技術研究報告. COMP, コンピュテーション 105(72), pp. 39-44, 2005. - Manindra Agrawal, Neeraj Kayal, Nitin Saxena.
PRIMES is in P,
Annals of Mathematics 160, no. 2, pp. 781–793, 2004.
草野 一彦