タギロンの NP 完全性
埜口未帆1(指導教員：長尾篤樹)

はじめに

3

本章では本稿での解析対象である “タギロン充足性問題” を定義する．
タギロン充足性問題の入力はタギロンの質問カードとその質問に対する答えの組を要素とする集合で表現する．ここで，推測対象の数字カードは t 枚あり，その並びにより左から順番に I1 , I2 ,. . . , It とする．また，数字カードに描かれる数字は 0 から n までとし，数字カードの色は c 色存在するとする．
さらに，推測対象の数字カードは数字が小さい方から左から並び，同一の数字に対しては色番号の小さい順に左から並んでいるとする．
質問は以下の三通りを考える．一つ目は特定の条件を満たすカードの位置の組を答える質問である．「5 はどこにあるか」「同じ色が隣り合っているカードはどこか」「数字が連続しているカードはどこか」「隣に同じ数字が存在するようなカードはどこにあるか」等がこれにあたる．これらの質問をクエリの形で表現するため，引数 a が 0〜n の場合はその引数がどこにあるか，引数が−1, −2, −3 のときはそれぞれ色の隣接，連続した数字，同一の数字に対する質問を表すとし，q1 (a) と表す．二つ目は特定の性質を持つ数字カードの枚数を答える質問である．「色 1 のカードは何枚あるか」「奇数は何枚あるか」等がこれにあたる．これらの質問をクエリの形で表現するため，引数 a が 1〜c の場合はその色の枚数を，0, −1 の場合はそれぞれ偶数，奇数の数字を持つ枚数を確認する質問を表すとし，q2 (a) と表す．三つ目は数字カードの色や位置の範囲を指定し合計値を返す質問である．「色 1，色 4 のカードの数字の合計値はいくつか」「小さい方から 3 つの数字の合計値はいくつか」等がこれにあたる．これらの質問をクエリの形で表現するため，第一引数は色の指定もしくは場所の指定を表し，第二引数以降はその指定する範囲だけ有限個を取る
ことし，例えば上述の二つの質問は q3 (”color”, 1, 2)，q3 (”position”, 1, 2, 3) と表すとする．
以上の 3 通りのクエリとその出力の組が列になったものをタギロン充足性問題の入力とする．入力すべてに対して整合性の取れる解答が存在する場合，タギロン充足性問題の出力は Yes に，どこかで矛盾が発生する
場合は出力 No となる．

理論計算機科学のひとつの分野である計算量理論分野では，ある問題を解決するために必要な計算量をその入力長に対しどの程度の規模となるかを議論の対象としている．最も多く研究されている計算量クラス NPとは，多項式時間限定非決定性チューリング機械で判定可能な問題の集合である．この非決定性計算が数独などのペンシルパズルの特徴と合致する事から多くのペンシルパズルがクラス NP であり，また NP 完全という性質を持つ事が知られている [3, 2]．
本稿では計算量クラスが既知ではない対戦型論理ゲーム “タギロン” に対し，計算量クラスの解析を行う．
タギロンは不完全情報二人対戦ゲームであり計算量解析が難しい事から，タギロンを一人ゲームへと変換したタギロン充足性問題での解析を行い，本問題が NP 完全である事を証明する．

2タギロン充足性問題

タギロン

タギロンとは，2017 年に JELLY JELLY GAMES
より発売された二人対戦ボードゲームである．ルールに沿って質問を投げかけ合い，先に相手の手札を正確に言い当てる事で勝敗が決まる．
手札には 0〜9 の数字が描かれた数字カードを用いる．0〜4, 6〜9 までの数字が描かれた赤色と青色の数字カードがそれぞれ 1 枚ずつ，5 の数字が描かれた黄色の数字カードが 2 枚存在する．それぞれのプレイヤーにはその 20 枚のカードから 5 枚ずつ手札として分配され，余りの 10 枚は伏せておく．各プレイヤーは自身の手札を左側に小さい数字が来るように整列させ，また 5以外の同じ数字が記載される数字カードが複数存在す
る場合は左側に赤色が来るように整列させる．
ゲームの目的は，相手プレイヤーの手札の並びを正確に当てる事である．目的を達成するために，場に質問カードが用意されている．質問カードは「特定の数字が書かれたカードの位置はどこか」「小さい方から 3つの数字の合計値はいくつか」等の質問内容が描かれ，24 枚存在する．そのうち 6 枚を表にし場に並べ，残りは山札として場に積んでおく．
ゲームの流れは以下の通りである．プレイヤーは交互に場に存在する質問カードから一枚選んで質問をし合い，その答えから相手の手札を推測していく．一度使用した質問カードは場から取り除き，場に存在する質問カードが常に 6 枚になるよう山札から補充する．自分の手番では「場に存在する質問カードから 1 枚を選んで質問」「相手の手札を言い当てる」二通りの行動のうちどちらかを必ず行い，質問を行った手番と同じ手番で相手の手札を言い当てることはできない．
1 章で述べた通り，二人対戦ゲームであるタギロンの計算量の解析を直接行うことは困難である．そのため，今回はタギロンの変種として「一人で行う」「複数質問カードとその返答から，整合性の取れるカードの並びを推測する」ゲーム考え，その計算量の解析を行う．

4

タギロン充足性問題の NP 完全性

本章では上記のように定式化されたタギロン充足性問題の NP 完全性を証明する．
Theorem 1. タギロン充足性問題は NP 完全である．

Proof. 定義より，本問題は明らかに NP に含まれる．
本問題の NP 困難性を示すため，NP 完全として知られる k-ハイパーユニフォームハイパーグラフの k色頂点被覆問題からの多項式時間帰着を行う．k-ユニフォームハイパーグラフとは，グラフの辺すべてが k個ずつの頂点の集合で表現されるグラフである．ハイパーグラフの頂点を k 色で各色は sk 頂点だけ塗り分

63

け，すべての辺に k 色で彩色した頂点が必ずひとつずつ存在するような色の付け方が存在するか Yes/No で判定する問題を k-ユニフォームハイパーグラフ上の k 色頂点被覆問題と呼ぶ．k-ユニフォームハイパーグラフ
上の k 色頂点被覆問題は Hitting Set Problem からの帰着を用いて NP 完全であることが知られている [1]．
k-ユニフォームハイパーグラフは，q1 (−3) = (. . . , {i=1ei = (vi1 , vi2 , . . . vik )として定義される．ただし，頂点集合 V も辺集合 E も有限集合である．
上述の k 色頂点被覆問題をタギロン充足性問題へと帰着させるため，以下のように k-ユニフォームハイパー
グラフをタギロン充足性問題の入力へと変換する．タギロン充足性問題ではハイパーグラフの辺と頂点に対し数字カードの色を 1 色ずつ対応させる．すなわち，数字カードの色は |V | 色となる．色番号は頂点そのものを用る．すなわち，i < j であれば色番号は vi < vj である．数字カードに描かれる数字は α1 , α2 , . . . , αk の k個とし，ハイパーグラフの頂点を塗り分ける色と対応していると考える．また，便宜上 α > max(s1 , . . . sk ) とする．
数字カードとその並びに対し，質問と返答の組もハイパーグラフからの変換で作成する．今回の帰着ではクエリ q1 (−3), q3 を用いる．
作成するクエリは 3 通りに分けられる．一つはある辺に着目し，辺が含む頂点に対応する k 色の数字カードの合計値を確認するクエリである．すべての辺に対して質問を行う必要があるため，合計 |E| 個作成する．
もう一つは全頂点への彩色結果に着目し，頂点に対応する |V | 色の数字カードの合計値を確認するクエリである．最後は彩色条件に着目し，同じ色を同じ数字に対応させるため，同一の数字が何個並んでいるか確認するクエリを用意する．
ハイパーグラフ上で，ある頂点 vi が色 t で彩色されている場合，帰着したタギロン充足性問題では vi 色，数字 αt の数字カードが存在するように各クエリの出力を調整する．このような調整が可能となるように，辺に対するクエリの出力を以下のように定義する．

q3 (”color”, vi1 , vi2 , . . . vik ) =α5si }, . . . )i=1sk >1

今後の課題

参考文献
[1] B. Escoﬃer, L. Gourvès, and J. Monnot. Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Journal of Discrete Algorithms, 8(1):36–49, 2010.
[2] C. Iwamoto, M. Haruishi, and T. Ibusuki. Computational complexity of herugolf and makaro.
IEICE TRANS. on Fundamentals of Electronics, Communications and Computer Sciences,102(9):1118–1125, 2019.
[3] T. Yato and t. Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE TRANS. on Fundamentals of Electronics, Communications and Computer Sciences, E86(A(5)):1052–1060, 2003.

j

上記の状況で頂点全体に着目すると，彩色後の状況では各頂点は色 k で sk 個ずつ彩色されている．この状況から，頂点に対するクエリの出力も以下のように定義できる．
k∑k∑

タギロン充足性問題は，整合性の取れる回答に複数の選択肢がある状況でも出力は Yes となる．一方，タギロンは相手の手札を正確に当てるゲームであり，回答を一つのみに絞り切るまでの計算量を解析することでよりタギロンに近づいた問題になると考えられる．

j=1

q3 (”color”, v1 , . . . , v|V | ) =si + 1, . . . ,これにより，k 種類の数字が小さい順に si 個ずつ並んでいることが確認できる．
これらの変換を用い，k-ユニフォームハイパーグラフ
上の k 色頂点被覆問題を |E| + 2 個のクエリとその出力の組を入力として持つタギロン充足性問題へと変換することができる．
k 色頂点被覆を持つ入力を変換した場合，そのグラフは k 色すべてについて，si 個ずつ頂点を彩色可能である．変換されたクエリそれぞれに対し，変換元の彩色に対応した数字カードの列は全て整合性が取れているものとなる．よって帰着後のタギロン充足性問題の出力は Yes となり正しく変換できている．
頂点被覆を満たすことができない入力から帰着した場合を考える．帰着後のタギロン充足性問題で，q1 (−3)のクエリとその出力に対して整合性が取れる回答が存在すると仮定する．変換元のグラフは頂点被覆を持たないため，辺に関するクエリのうち少なくとも一つは満たされない．よって，整合性が取れる回答は存在せず，正しく変換できている．
以上によって，k-ユニフォームハイパーグラフ上の k色頂点被覆問題をタギロン充足性問題へ帰着をすることができた．
また，タギロン充足性問題における入力長は O(|E|)
であり，クエリそれぞれに対し高々 k + 1 種類の色のカードの合計値を確かめるだけでよい．この行程はO(k|E|) で行えるものである．よって k-ユニフォームハイパーグラフ上の k 色頂点被覆問題からの多項式時間帰着が行えており，タギロン充足性問題は NP 完全である．

H = (V, E), V = (v1 , v2 , . . . ), E = (e1 , e2 , . . . ),

k∑

k−1
∑

(sj × αj )j=1

最後に，色に対して数字を割り当てるため，q1 (−3)
を用いることにより，同じ数字がそれぞれ何個ずつ存在するかを確認することができる．その状況から，si > 1である si を用いクエリの出力を以下のように定義する．

64