2プレイヤーゲームは多項式空間完全

Question

したがって、n×nのゲームボードがあり、ボード上の各位置には整数があります。プレーヤー1は行1から番号を選び、プレーヤー2は行2から番号を選び、それ以上行がなくなるまで交互にします。次に、それらがすべての数字を加算し、合計が所定の合計Sに等しい場合、プレイヤー1が勝ち、プレーヤー2が勝ちます。特定のボードおよび合計（B、S）に対する選手1の勝利戦略は、選手1が何者2が何であっても勝つことができる場合である。 この問題はPSpaceで完全であることを示したい

最初に、PSpaceに表示されている必要があります。これは、動きの総数がボードのサイズn^2。

私はQSATから減らなければならないことは分かっていますが、PSpaceは難しいことを示すことに固執していますが、どのように解決できないのでしょうか。助けてもらえますか？

編集実際に私はQSATから減らさなければならないことは分かりませんが、周りを検索した後でQSATが最も有望な候補に見えます。他の多くの2人プレイゲーム、Geographyが最も顕著な例であるが、QSATからは減るので、私はこれも必要であると考えた。しかし、もし私がこれについて間違っていれば、私を修正してください。

Answer 1

QSATから削減を選択した場合、タスクは数式で始まります。

プレイヤー1が勝利戦略を持っている場合、この式の否定が正確に同値であるようにゲームのインスタンスを構築する必要があります。プレーヤー2の役割は、主に普遍的に定量化されたブール変数の評価を固定することです。プレイヤ1は、現存量化されたブール変数に関して同様の役割を有する。

トートロジーの場合にプレーヤ1がゼロサムのみを強制できるようにテーブルを作成するには工夫が必要です。また、必要なテーブル行の数は、数式内の数量化関数の数が線形であることを確認してください。

[スポイラー1開始] 宿題モードで議論することを忘れないでください。ほとんどすべての詳細をヒントに追加しますが、詳細を理解すれば見つけられると思われる3つの技術的な欠陥をこのソリューションに隠します。できるだけ多くのものを見つけて、あなたのコメントをできるだけ多く修正してください。

まず、ゲーム理論の用語でQSATを見てください。一般性を失うことなく、定量化されたブールセンテンス（自由変数を持たない公式）がすべての量子を前面に書いていると仮定します。最初に少数の現存する定量化された変数、次に少数の普遍的な変数、次にもう一つの実存的なブロックなどがあります。最初のプレイヤーは、特定のブール値を最初に数えきれない数量化された変数に代入（代入）して再生を開始します（置換後の数式が最も左のユニバーサル量限定子で始まる場合にのみ停止します）プレイヤー1は元々第2の存在量のブロックであったものを処理するなど、プレイヤー1はすべての変数が指定された後に「真」と評価されれば勝ち、そうでなければプレイヤー2が勝ちます。このQSATゲームは、式のコーディングを前提とすると数値的に再生することもできるので、各式は構文に基づいて一意の数値を持つようになります（式から数を数式から効率的に求めることができます）。数式を交換すると、プレイヤーは数字を交換します（formul aコード）。

ここで、このQSATのようなゲームをあなたのボードゲームに変換したいと考えています。各行は、1人のプレイヤーの移動を表します（同じタイプの数量子の1ブロック分）。行の各位置は、前の行の任意の位置からのそのプレーヤーの可能な移動を表します。具体的には、移動によって作られたの差：移動後の式のコードから移動前の式のコードを引いたものです。このようにして、実行中の合計は、ゲームの与えられたフェーズに立つときの式と常に等しくなります。

特別な例外として、式trueのコードをさらに減算することによって、最後の行のすべての場所を変更します。このようにして、完成したボードゲームの合計は、プレーヤー1が勝った場合は0になり、そうでない場合は0になります。これは、あなたのボードゲームに対する定量化された公式のトートロゴの望ましい低減です。 [スポイラー1終了]