一般地理

計算複雑性理論では、一般化地理学はPSPACE 完全問題としてよく知られています。

地理は、プレーヤーが順番に世界中の都市の名前を挙げる子供向けゲームです。選ばれた各都市は、前の都市名の末尾と同じ文字で始まっていなければなりません。重複は許可されません。ゲームは任意の開始都市から始まり、プレーヤーが続行できずに負けると終了します。

ゲームを視覚化するために、世界の各都市をノードとする有向グラフを作成できます。都市ラベルN 2 が都市ラベル ノードN ₁の名前の末尾の文字で始まる場合にのみ、ノードN ₁からノードN _{2に矢印が追加されます。言い換えると、ゲームのルールに従って最初の都市から 2 番目の都市につながることができる場合、 1}つの都市から別の都市に矢印を描きます。有向グラフの各交互エッジは、各プレーヤーに対応します (2 人のプレーヤー ゲームの場合)。パスを延長できない最初のプレーヤーが負けます。ゲームの図 (ミシガン州のいくつかの都市を含む) を下の図に示します。

一般化地理 (GG) ゲームでは、都市名のグラフを任意の有向グラフに置き換えます。次のグラフは、一般化地理ゲームの例です。

P _{1 を}最初に動くプレイヤー、P _{2 を}2 番目に動くプレイヤーと定義し、ノードをN ₁からN _nと名付けます。上の図では、P _{1 の}勝利戦略は次のとおりです。 N _{1 はノード}N ₂とN ₃のみを指しています。したがって、P ₁の最初の動きは、これら 2 つの選択肢のいずれかでなければなりません。P _{1 は}N ₂を選択します( P _{1 が}N _{3 を}選択した場合、P _{2 は}N _{9 を}選択するでしょう。それが唯一の選択肢であり、P _{1 は}負けます)。次に、P _{2 は}N 4 を選択します。それが唯一の選択肢であるためです。ここで P 1 は N _{5 を}選択し 、続い_てP ₂はN 3 または N 7 を選択します。_P 2_の選択に_関係なく_、P 1はN ₉を_選択し、P ₂には選択肢が残っていないため、ゲームに負けます。

一般化された地理ゲームにおいてどのプレイヤーが勝利戦略を持っているかを決定する問題はPSPACE 完全です。

GG = { ⟨ G , b ⟩ | P _{1 は、グラフ}G上のノードbから始まる一般化地理ゲームで勝利する戦略を持っているとします。GG ∈ PSPACEであることを示すために、どのプレーヤーが勝利戦略を持っているかを決定する多項式空間の再帰アルゴリズムを示します。GG のインスタンス ⟨ G , n _start ⟩ ( Gは有向グラフ、n _startは指定された開始ノード) が与えられた場合、アルゴリズムM は次のように進行します。

M (⟨ G , n _start ⟩) について:

1. ノードn _startの出次数を測定します。この次数が 0 の場合、プレイヤー 1 に利用できる移動がないため、denyを返します。
2. nから 1 つ_のエッジで到達可能なすべてのノードのリストを構築します: n ₁、n ₂、...、n _i。
3. Gからn _startとそれに接続されているすべてのエッジを削除して、 G ₁を形成します。
4. リストn ₁ , ..., n _i内の各ノードn _jについて、M (⟨ G ₁ , n _j ⟩)を呼び出します。
5. これらの呼び出しがすべてaccept を返す場合、P _{1 が}どのような決定を下しても、P _{2 に}は勝つための戦略があるため、accept を返します。それ以外の場合 (呼び出しの 1 つがdeny を返す場合)、P _{1 には}P ₂の成功する戦略をすべて拒否する選択肢があるため、 accept を返します。

アルゴリズムM は明らかに GG を決定します。消費される唯一の非自明な多項式ワークスペースは再帰スタック内であるため、これはPSPACE内にあります。再帰スタックによって消費されるスペースは多項式です。再帰の各レベルでスタックに 1 つのノードが追加され、レベルは最大でn個あるためです。ここでn はG内のノードの数です。これは本質的に深さ優先探索と同等です。

以下の証明はデイヴィッド・リヒテンシュタインとマイケル・シプサーによるものです。^[1]

GG のPSPACE 困難性を証明するために、FORMULA-GAME問題 ( PSPACE 困難であることが知られている) を多項式時間 ( P ) で GG に簡約することができます。簡単に言うと、FORMULA-GAME 問題のインスタンスは、量化されたブール式φ = ∃ x ₁ ∀ x ₂ ∃ x ₃ ... Qx _k (ψ) で構成されます。ここで、Q は∃ または ∀ です。このゲームは、P _aとP _{e の}2 人のプレーヤーによって行われ、プレーヤーは交互に連続するx _iの値を選択します。式 ψ が真になった場合はP _{e が}勝ち、 ψ が偽になった場合はP _{a が}勝ちます。式 ψ は、連言正規形であると想定されます。

この証明では、簡潔にするために、量指定子リストが存在修飾子 ∃ で始まり、存在修飾子 ∃ で終わると仮定します。 ψ に現れないダミー変数を追加することで、任意の式をこの形式に変換できることに注意してください。

上記のようなグラフG を構築することで、FORMULA-GAME の任意のインスタンスを一般化地理のインスタンスに縮小できることを示します。ここで、 P ₁の最適戦略はP _eの最適戦略と同等であり、P ₂の最適戦略はP _aの最適戦略と同等です。

左の垂直のノード チェーンは、FORMULA-GAME で変数の値を選択する手順を模倣するように設計されています。各ダイヤモンド構造は、量化された変数に対応します。プレーヤーは、各分岐ノードで順番にパスを決定します。最初の量化子は存在的であると想定したため、P _{1 が}最初に進み、x ₁がtrueの場合は左のノードを選択し、x ₁がfalseの場合は右のノードを選択します。次に、各プレーヤーは強制的に順番を回らなければならず、次にP _{2 が}x ₂の値を選択します。これらの交互の割り当ては、左側に沿って続きます。両方のプレーヤーがすべてのダイヤモンドを通過した後、最後の量化子は存在的であると想定したため、 再びP _{1の番になります。} P _{1 は}、グラフの右側へのパスをたどるしかありません。次に、P ₂が移動する番になります。

プレイがグラフの右側に到達すると、フォーミュラ ゲームでのプレイ終了と似た状態になります。フォーミュラ ゲームでは、 ψ がtrueの場合はP _{e が}勝ち、ψ がfalseの場合はP _{a が}勝つことを思い出してください。グラフの右側では、P _{e が}勝つ場合にのみP _{1 が}勝ち、P _{a が}勝つ場合にのみP _{2 が}勝つことが保証されます。

まず、 P _{a が}勝つとP _{2 も}必ず勝つことを示します。P _{a が}勝つ場合、 ψ はfalseです。 ψ がfalse の場合、不満足な節が存在します。 P _{2 は勝つために不満足な節を選択します。次に、} P ₁の番になると、P ₂が選択した節のリテラルを選択する必要があります。 節内のすべてのリテラルはfalseであるため、左の垂直チェーンで以前に訪問したノードに接続しません。これにより、 P _{2 は}左チェーンのダイヤモンド内の対応するノードへの接続をたどり、それを選択できます。ただし、P ₁は隣接するノードを選択できなくなり、負けます。

ここで、 P _{e が}勝ったときはP _{1 が}常に勝つことを示します。P _{e が}勝った場合、 ψ は真です。 ψ が真であれば、グラフの右側のすべての節に真のリテラルが含まれます。 P _{2 は}任意の節を選択できます。次に、P _{1 は}真であるリテラルを選択します。そして、それが真であるため、左の垂直ノードの隣接するノードはすでに選択されており、P _{2 は}移動することができず、負けます。

一般化された地理学は、平面グラフ上でプレイする場合でもPSPACE完全です。次の証明は^{[1]の定理3からのものです。}

平面 GG は GG の特殊なケースであり、GG は PSPACE 内にあるため、平面 GG は PSPACE 内にあります。平面 GG が PSPACE 困難であることを示すことが残っています。これは、任意のグラフを平面グラフに変換する方法を示して、このグラフでプレイされる GG ゲームが元のグラフと同じ結果になるようにすることで証明できます。

それには、元のグラフのすべてのエッジ交差をなくすだけで済みます。3 つのエッジが 1 点で交差しないように、また交差エッジのペアが同じゲームで使用できないようにグラフを描きます。これは一般には不可能ですが、FORMULA-GAME インスタンスから構築されたグラフでは常に可能です。たとえば、交差に関係する節の頂点からのエッジのみを持つことができます。ここで、各交差を次の構成に置き換えます。

結果は平面グラフで、元のグラフと同様に同じプレイヤーが勝利を強制できます。つまり、プレイヤーが変換されたゲームで V から「上」に移動することを選択した場合、両方のプレイヤーは W まで「上」に移動し続けるか、すぐに負けるかのいずれかになります。したがって、変換されたゲームで V から「上」に移動することは、元のゲームでの V→W の移動をシミュレートします。V→W が勝利の動きである場合、変換されたゲームで V から「上」に移動することも勝利の動きであり、その逆も同様です。

したがって、変換されたグラフでプレイされる GG ゲームは、元のグラフと同じ結果になります。この変換には、元のグラフのエッジ交差の数の定数倍の時間がかかるため、多項式時間がかかります。

したがって、平面 GG は PSPACE 完全です。

最大次数が3の平面二部グラフ上で行われるGGは、次数が3を超える頂点を次数が最大3の頂点の連鎖に置き換えることで、依然としてPSPACE完全である。証明は^[1]にあり、次の構成を使用する。

一方のプレイヤーがこの構造への入口のいずれかを使用する場合、もう一方のプレイヤーがどの出口を使用するかを選択します。また、中央の頂点は常に訪問されるため、構造を通過できるのは 1 回だけです。したがって、この構造は元の頂点と同等です。

GG のバリエーションはエッジ ジオグラフィーと呼ばれ、各移動後にプレイヤーが通過したエッジが消去されます。これは、各移動後にプレイヤーがいた頂点が消去されるオリジナルの GG とは対照的です。この観点から、オリジナルの GG は頂点ジオグラフィーと呼ぶことができます。

エッジ地理はPSPACE完全です。これは頂点地理に使用されたのと同じ構成を使用して証明できます。^[2]

また、無向グラフ（つまり、両方向にエッジをトラバースできるグラフ）でいずれかの地理ゲームをプレイすることも考えられます。Fraenkel、Scheinerman、Ullman ^{[3] は、}無向頂点地理は多項式時間で解くことができるのに対し、無向エッジ地理は最大次数が 3 の平面グラフであっても PSPACE 完全であることを示しています。グラフが二部グラフの場合、無向エッジ地理は多項式時間で解くことができます。

GG がPSPACE 完全であることを考えると、 P = PSPACEでない限り、 GG での最適プレイのための多項式時間アルゴリズムは存在しません。ただし、特定のゲーム (チェスなど) には有限の数のゲーム ポジションが含まれるため、他のゲームの複雑さを証明するのはそれほど簡単ではない可能性があります。そのため、 PSPACE 完全な問題へのマッピングを定式化することは困難 (または不可能) です。それにもかかわらず、特定のゲームの複雑さは、一般化 (たとえば、 n × n のボードへの) によって分析できます。GG の完全性の証明の帰結として、一般化されたGoの証明については、参考文献を参照してください。

• マイケル・シプサー、『計算理論入門』、PWS、1997年。