タギロンの ASP 完全性
芳賀朋恵

1(指導教員：長尾篤樹)

はじめに理論計算機科学では，パズルやボードゲームの計算量に関して多くの研究が行われている [1]．最もよく研究されている計算量クラスに NP がある．NP 完全性はNP に含まれ、かつ任意の NP 完全な問題から多項式時間帰着可能であることで示される．パズルやボードゲームの計算量解析は，それらのルールの特徴によって NP に含まれる場合が多いため，その完全性が研究対象とされている．
特にパズルでは，解が存在することに加えて唯一解であることが望まれる．唯一解を持つ問題か判定するには，別解の存在を確認すれば良い．別解の存在を確認する問題は，Another Solution Problem（以下，ASP と記す．）という概念で知られている．ASP 完全性が示せれば，別解の存在性が判定できるため，唯一解を持つ問題であるかが判定可能となる．
本稿では，解の存在を確認することが難しい問題に対して，その唯一解を確認することも難しいことを証明する．そこで，NP 完全であることが示されている論理
ボードゲーム タギロン を充足性問題へと変換した問題に関して ASP 完全性を示す．

2

数学的準備

2.1

タギロン充足性問題

タギロンは，二人対戦型論理ボードゲームである．色と数字を持つカードのうち 5 枚を手札とし，プレイヤーたちが交互に相手の手札に関する質問をしていき，先に相手の手札の色および数字とその並びを正確に言い当てることができた方が勝利となる．ゲームで勝つためには，質問とその答えとの整合性の取れるカードの並びが存在することを確認する必要がある．カードの並べ方は色と数字による制限があるため，5 枚の手札の色と数字が分かれば並びは一意に決まる．例えば，図 1
は質問とそれらと整合性が取れている手札の例である．
この例では，5 つの質問とその答えにより一意なカードの並びを導き出し，解にたどり着くことができている．

タギロン充足性問題の入力は，質問とそれに対する答えの組を要素とする集合で表現されている．推測対象のカードの枚数は n 枚，書かれている数字はα1 , α2 , ..., αn ，色は 1〜c という色番号で表現されている．カードは数字や色番号の数が小さいほど左に並べるとされている．そして，質問はクエリの形，質問の答えはクエリの出力として表現されている．例えば，「色番号 1 のカードの合計値はいくつか？」という質問に対し，答えが 11 の場合は q(色 1 の合計値) = 11 と表現される．また，「8 のカードは何枚あるか？」という質問に対し，答えが 1 枚の場合は q(8 の枚数) = 1 と表現される．入力すべてに対して整合性の取れるカードの並びが存在する場合はタギロン充足性問題の出力はYes，そのようなカードの並びが存在しない場合は出力が No となるとされている．
以上より，タギロン充足性問題は入力：クエリとその答えの組の列
出力：入力に対して，整合性の取れる解が存在する
場合は Yes/存在しない場合は Noとして定義される．
タギロンでは正しい解を先に宣言できた方が勝利となる．そのため，解が一つ存在することがわかってもその段階で別解も存在するかどうか考える必要がある．
例えば，図 1 において最初の 3 つの質問とその答えだ
けでは図 1 の手札とは異なる手札が別解として考えられる（図 2）．これらのことから，タギロンをプレイする上で別解の存在性を考えることはとても重要であると言える．

ある問題に対して別解の存在を確認する問題は，ASP という概念で知られている．ASP が NP 完全であるとき，その問題は「ASP 完全である」と言う．
2.2

タギロンを一人ゲームに制限した タギロン充足性問
題 は 2019 年に埜口によって NP 完全であることが示されている [2]．

ASP 完全性ある問題に対してインスタンスとその問題の解が入力として与えられたとき，入力した解とは異なる解，すなわち別解を見つける問題が NP 完全であれば，その問題は ASP 完全であると言う．ASP 完全性は, ASP完全であると知られている問題（以下，ASP 完全問題と記す．）からの帰着が存在すれば示すことができる．
ASP 完全問題からの帰着は，インスタンスとして与えられる入力だけでなく解も単射として変換される必要がある．出力に関しては，帰着先の出力をそのまま帰着元の出力として扱うため，変換は行わない．このような特徴を持つ多項式時間帰着を ASP 帰着 と言う．図
3 は NP 完全性を示すための多項式時間帰着と，ASP帰着の違いを比較したものである．

) = N というクエリとその答えの組に変換する．
∑n2. 集合 X 内の数の和を M （= i=1 ai ）とした時，
M − N をタギロンの色番号 2 のカードの合計値とする．すなわち，q(色 2 の合計値) = M − N というクエリとその答えの組に変換する．

3. 集合 X の要素をタギロンのカードの数字とする．
よって，数字 k(∈ a) が何枚存在するかという質問に対して答えが m 枚だった場合は，q(k の枚数) = m というクエリとその答えの組に変換する．

3

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

本章では，先行研究で定義されたタギロン充足性問題を用いて，その ASP 完全性を証明する．
本問題の ASP 完全性を示すため， 部分和問題 からの ASP 帰着を行う．部分和問題は，入力として整数 N と m 個の整数 a1 , a2 , ..., am が与えられる．そして，a1 , a2 , ..., am から部分集合を選択し，その集合に含まれる数の和（以下，部分和と記す．
）が N と等しくなるかどうかを判定する．N と部分和が等しくなるような部分集合が存在する場合は Yes を，1 つも存在しない場合は No を出力する．よって部分和問題は以下のように定義される．
入力：整数 N ，X = {a1 , ..., am | a ∈ Z，m ∈ N}
∑j′
出力：S =i=1 ai となるような部分集合 S ={a1 ′ , ..., aj ′ | S ⊆ X ，j ∈ N} が存在する場合はYes/存在しない場合は No
部分和問題は，3 CNF Satisﬁability Problem（以下，3-SAT と記す．）からの多項式時間帰着により NP 完全であることが示されている [3]．3-SAT は ASP 完全問題であることが知られている [1] ため，この帰着がASP 帰着になっていることが確認できれば部分和問題は ASP 完全問題であると言うことができる．3-SATから部分和問題への帰着は 3-SAT の解を部分和問題の解への単射を自然と導くので，部分和問題は ASP 完全であることが確認できる．部分和問題は，入力が正の整数に限定されても ASP 完全である．
以上を踏まえ，タギロン充足性問題の ASP 帰着を示す．
Theorem 1. タギ ロン 充 足性問 題 は ASP 完全である．

Proof. 本問題の ASP 完全性を示すため，部分和問題からタギロン充足性問題への ASP 帰着を行う．
部分和問題の入力として，インスタンス N (∈ N)，X = {a1 , ..., am | a，m ∈ N} と解 Y = {a1 ′ , ..., ai ′ |Y ⊆ X}（ただし i ≤ m）を与える．
部分和問題をタギロン充足性問題へ帰着させるため，上述の入力をタギロン充足性問題の入力に変換する．
変換は以下のように行う．

1. 部分和問題の入力 N をタギロンの色番号 1 のカードの合計値とする．すなわち，q(色 1 の合計値以上の変換により，部分和問題のインスタンスをタギロン充足性問題のインスタンスへと書き換えることができる．また，部分和問題の入力として与えられた解は，上記 1〜3 で判明した数字および色番号が小さい順に左から並べることでタギロンの解へと変換できる．
タギロン充足性問題の入力のクエリとその答えの組は高々 m + 2 種類である．
一方で，整数 a を表すための文字数が t 文字だった
場合，部分和問題の入力長は n = O(tm) となる．よって，上述の変換は O(n) で行えるものであるため，部分和問題からタギロン充足性問題へ線形時間で帰着が行えていることが確認できる．
この帰着により，タギロン充足性問題の入力と整合性が取れる別解が存在すれば部分和問題の別解も存在することが確認できる．また，整合性の取れる別解が存在しない場合は部分和問題の別解も存在しないことが確認できる．
以上により，部分和問題からタギロン充足性問題へASP 帰着の存在が確認できた．よって，タギロン充足性問題は ASP 完全である．

4

まとめと今後の課題

本研究では，タギロン充足性問題の ASP 完全性を示すために 2 つの ASP 帰着を示した．1 つ目として，ASP 完全であると知られている 3-SAT から部分和問
題への帰着が ASP 帰着であることを確認し，部分和問題が ASP 完全であることを示した．2 つ目は，部分和問題からタギロン充足性問題への ASP 帰着を構成し，タギロン充足性問題が ASP 完全であることを示すことができた．
「数字をグループに分割する」という特徴を持つ他のゲームも部分和問題からの帰着で ASP 完全性を示せると考えられるため，タギロン以外のボードゲームに関しても同様に ASP 完全性を示す帰着が考えられる．

参考文献[1] Takayuki Yato and Takahiro Seta. Complexity
and completeness of ﬁnding another solution andits application to puzzles. IEICE transactions on
fundamentals of electronics, communications andcomputer sciences, Vol. 86, No. 5, pp. 1052–1060,
2003.
[2] 埜口未帆. タギロンのＮＰ完全性. お茶の水女子大学卒業研究要旨, 2019.
[3] Sanjeev Arora and Boaz Barak. Computational
complexity: a modern approach. Cambridge University Press, 2009.