今日、様々なゲーム・パズルが世界中で遊ばれている。特に、近年における「数独」等の「ペンシルパズル」の流行を受けて、パズルの問題をいかにして作るかというととが重要な課題になってきている。本論文では、「別解問題」(Another Solution Problem ;略称ASP)について研究する。ASPとは、問題のインスタンスとそれに対する解が与えられた時に与えられたもの以外の解を求める問題のことであり、パズル問題の作成の作業と深い関わりがある。

ASPの計算量解析への系統的なアプローチは、FNP(NPの関数版)においては、1996年の上田・永尾の論文に始まる。そこでは、p紅白momous還元で解の間の変換が効率的に行えるものがASPの計算量の解析に有用であるととが指摘された。

本研究では彼等の考えを拡張して、ASPの計算量を系統的に調べるための枠組を構築する。ASPでは解が本質的な関わりをもつので、この枠組は(多価)関数計算量の理論に基づくことになる。我々が提案する枠組における主要な道具となるものは、上回・永尾が用いた還元をより強くした還元である関数p紅白血.onlOUS還元と、関数計算量クラスの中でのその還元に関する完全性として定義されるASP完全性である。ある問題がASP完全であるζ とからはASPが(判定問題あるいは関数問題として)難しいことが導出される。とれによって、実際にASPそのものについて調べることなくASPの困難性の結果を得ることができるようになる。パズル問題作成のような実用的な関心と関わりのあるASPの理論において関数計算量が重要な役割を果たすことは、関数計算量の研究が主に理論的興味から行われτきたζ とを考えると興味深い。

そして、その枠組みを様々なゲーム・パズルに適用する乙とを考える。ゲーム・パズルは判定問題としてはNP、PSPACE、EXP(指数時間)のクラスに属している。クラスNPにおいては数独などの幾つかのペンシルパズルがASP完全であることを示す。

ASPの理論そのものは特定の計算量クラスに依存しないようにできているが、その理論をNPより高いクラスに適用しようとすると、幾つかの間題が生じる。最大の問題は、高い言語クラスに対応する適切な関数クラスの定義がないことである。

クラスPSPACEに対する最初の試みとして、パズルゲームの一種の「倉庫番」を取り上げる。これは、長い手数の1人ゲームの例になっている。我々は、新しい種類の非決定性変換機であるOB変換機を提案し、それを用いてクラスFNPSPACE(p_out)を定義する。乙のクラスは倉庫番の解の性質と適合するように作られていて、それ故、倉庫番がこのクラスでASP完全となることが期待される。我々は、倉庫番を3次元に拡張したゲームが実際にFNPSPACE(p-out)でASP完全となることを証明する。さらに、短い手数の2人ゲームの例となる人工的ゲームであるQBFゲームについてもFNPSPACE(p_out)でASP完全であることを証明する。

クラスEXPは長い手数の2人ゲームに対応する。このクラスでは我々は一般化詰将棋の余諮問題を対象にする。余詰問題はパズルとして確固とした解の定義をもっていて、この定義においては解老多項式時間で検証することができない。我々は、このことがASPの理論を適用するときに大きな問題となることを議論し、その上で、この問題を解決するために、ASPの理論をプロミス問題を扱えるように拡張する。そして、拡張された理論を用いて、余詰閣題が指数時間困難であると之を証明する。最後に、長い手数の2人ゲームに対応する関数閣題クラスを定義する方法について議論する。

本研究において得られた困難性の結果は、これらのゲームやパズルの問題を作成するととが問題を解くことと同様に難しい乙とを示唆している。

計算量理論は計算機の誕生から深く研究されてきた,コンピュータ科学のもっとも基本的かつもっとも重要な研究領域のひとつである.そのなかで P≠NP という予想は研究の最大の興味であり,推進力でもあったと言えるが,ここで P や NP といった問題クラスは「判定問題」として定義されるものである.すなわち,Yes か No かで答えられる問題,あるいは与えられた問題に対してある条件を満たす解が存在するか否かだけを問う問題設定であって,その具体的な解を要求する問題設定ではない.これに対して,与えられた問題に対する具体的な解を求めるという問題は計算量理論の世界では「関数問題」と呼ばれており,この関数問題について考えることは,判定問題という視点に新たな光を投げかけるものであるとともに,実用上でも有用なものである.本研究は,ゲームやパズルの問題に対して,出題者が意図した解以外の別解を探すという「別解問題」をターゲットとして,関数問題という視点から計算量の理論を展開した研究である.本研究は,計算量理論の進展に寄与するとともに,近年盛んになっているパズル業界に対して実用的な貢献をもなしうる成果と言える.

本論文は以下に概略を示す7つの章から構成されている.

1章では,まず対象として選定したゲームやパズルに対する情報科学的興味について論じられている.なかでもチェスやチェッカーは,コンピュータ科学を代表する偉大な研究者を含む,多くの研究者によって長年研究されてきている.本研究ではゲームやパズルを,プレイヤーの数(1人または2人)と手数の長さ(多項式時間または多項式領域)により4つのカテゴリに分類している.これらのゲームやパズルの通常の意味での解を求める判定問題については,すでに多くのものについて計算量クラスが特定されている.また,別解問題の先行研究として,Ueda と Nagao の研究成果が紹介されている.別解問題とは,問題とともに作者が意図した解が与えられ,与えられた解以外の解が存在するかどうかを考察する問題である.Ueda と Nagao らの研究は,解の個数を変えない問題の変換である parsimonious 還元を重要な道具として用い,解の存在について議論する判定問題の範疇での研究であった.これに対して,本研究では,関数問題としてゲーム(パズル)の別解問題をとらえ,さらにゲーム・パズルの4つのカテゴリすべてに対して別解問題の関数問題としての計算量の理論を打ち立てようとするものであることが示される.

2章では,関数問題の定義と基本的諸概念および計算量クラスが紹介される.これに加えて,計算量理論におけるプロミス問題の概念とそれに関する計算量理論について,さらに,2人ゲームの数学的定式化とその必勝戦略の表現の一つであるトレースの概念について,それぞれ導入されている.

3章では,著者によるゲーム・パズルの別解問題の基礎理論が展開される.まず,別解問題を定義する.すなわち,問題とともに n 個の解が与えられた時に,それ以外の解を求める関数問題として,n-別解問題を定義する.さらに,Ueda と Nagao らが用いた parsimonious 還元を,関数問題の計算量解析に適用可能な「関数 parsimonious 還元」に発展させ,それを用いて別解問題に関する完全性である ASP-完全性を定義する.ここで関数 parsimonious 還元とは,問題の変換により解の個数が変わらないだけではなく,片方の解から他方の解が多項式時間で計算できるような還元として定義される.ASP-完全性はある計算量クラスを従えて定義されるものであるが,計算量クラスとそこでの ASP-完全問題を適切に選択することにより,「この計算量クラスにおける ASP-完全な問題は,(ひとつも解が与えられていない)本来の問題と別解問題の両方について計算が困難である」となることが導出される.

4章から6章にかけては,1章で導入したゲーム・パズルの4つのカテゴリにおける別解問題の具体的議論が展開される.まず4章では,多項式時間1人ゲームが取り上げられる.このカテゴリに関係する計算量として著者は FNP と呼ばれるクラスを選択している.これは,多項式均衡かつ多項式時間で解が検証可能な問題クラスである.そのうえで,sat およびその変種が ASP-FNP 完全であることを示し,これからの関数 parsimonious 還元を示すことにより,「数独」,「スリザーリンク」,「フィルオミノ」という3つの代表的なパズルが ASP-FNP 完全であることを証明した.

続いて5章では,多項式領域1人ゲームと多項式時間2人ゲームについて議論される.多項式領域1人ゲームにおいては,手数が入力サイズに対して多項式時間で収まるとは限らないが,解の検証は入力の多項式時間で可能である.従って,このような性質を備えた関数問題の計算量クラスを新たに定義する必要がある.これに対して本研究では非決定性の履歴を出力する特殊な OB 変換機を導入し,その領域を入力の多項式限定,時間を出力の多項式限定とすることにより,この問題を解決することを提案する.さらに,こうして構築された計算量クラス(FNPSPACE(p-out))に対して,「倉庫番」というパズルの3次元版が ASP-FNPSPACE(p-out)完全であることを証明し,このカテゴリにおいても著者の別解問題理論が適用できることを実証している.また,多項式時間2人ゲームでも,「QBFGame」というゲームが同様に ASP-FNPSPACE(p-out)完全であることを示している.これに加えて,Savitch の定理の関数問題クラス版ともいえるもの,すなわち,FPSPACE(p-out) と FNPSPACE(p-out) が同じであることを証明している.これにより,この困難性のクラスにおいては,決定性機械でも非決定性機械でも同じ能力であることが分かる.

続いて6章では,多項式領域2人ゲームについて論じられる.このカテゴリでは,一般化詰将棋の別解問題である「余詰問題」を取り上げるが,詰将棋で伝統的に用いられている解の定義では,解の検証は入力の多項式時間ではできない.これに対して本研究では,与えられた解は正しいものと仮定して検証を省略できるプロミス問題の概念を利用する.その上で,別解問題の理論の適用として余詰問題が Prom-EXP 完全であることを証明した.これは判定問題の範疇であって,関数問題に拡張はできていないが,それに向けての大きな貢献と言える.

最後に7章では,研究成果を総括し,今後の研究の展望を述べて,論文を締めくくっている.

以上のように,本論文はゲームとパズルの別解問題を統一的に扱う理論を構築し,具体的なゲームやパズルの別解問題の計算困難性を証明することを通して,ゲームやパズルの理論に極めて大きな貢献をしたものと言える.また,本研究は長い歴史を持つ計算量理論に対しても複数の重要な貢献をしており,審査委員会は,本研究は博士号に十分値するものであると判断した.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。