論文の概要: Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography

• arxiv url: http://arxiv.org/abs/2106.02114v1
• Date: Thu, 3 Jun 2021 20:13:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 14:53:50.877392
• Title: Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
• Title（参考訳）: 敗戦(戦略的)による戦争勝利:無向地理における不名誉価値の複雑さの解決
• Authors: Kyle Burke, Matthew Ferland, Shanghua Teng
• Abstract要約: 我々は,非方向性地理学のグランディ値が計算に完全であることを証明した。 初めて、Grundy値$ast n$ と size in n でundirected Geographyインスタンスを構築する方法を示す。
• 参考スコア（独自算出の注目度）: 1.471992435706872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimber) of Undirected Geography is PSPACE-complete to compute. This exhibits a stark contrast with a result from 1993 that Undirected Geography is polynomial-time solvable. By distilling to a simple reduction, our proof further establishes a dichotomy theorem, providing a "phase transition to intractability" in Grundy-value computation, sharply characterized by a maximum degree of four: The Grundy value of Undirected Geography over any degree-three graph is polynomial-time computable, but over degree-four graphs-even when planar and bipartite-is PSPACE-hard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value $\ast n$ and size polynomial in n. We strengthen a result from 1981 showing that sums of tractable partisan games are PSPACE-complete in two fundamental ways. First, since Undirected Geography is an impartial ruleset, we extend the hardness of sums to impartial games, a strict subset of partisan. Second, the 1981 construction is not built from a natural ruleset, instead using a long sum of tailored short-depth game positions. We use the sum of two Undirected Geography positions to create our hard instances. Our result also has computational implications to Sprague-Grundy Theory (1930s) which shows that the Grundy value of the disjunctive sum of any two impartial games can be computed-in polynomial time-from their Grundy values. In contrast, we prove that assuming PSPACE $\neq$ P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum.
• Abstract（参考訳）: 1981年と1993年の組合せゲーム理論(CGT)以来の2つの長年にわたる複雑性理論的疑問を解決した。 Grundy値(a.k.a)を証明する。 Undirected Geography の nim-value または nimber は計算に PSPACE 完全である。 これは1993年の無向地理が多項式時間可解であるという結果とは全く対照的である。 簡単な減算に留意することで、我々はさらに二分法定理を確立し、Grundy-valueの計算において「誘引性への位相遷移」を提供し、最大次数が4である: 任意の次数3のグラフ上の非方向地理学のグランディ値は多項式時間計算可能であるが、平面グラフと二部グラフがPSPACEハードであるときでさえ、次数4のグラフを超越する。 さらに,まず,n におけるグランディ値 $\ast n$ と大きさ多項式による無向な地理インスタンスの構築方法を示す。1981 年の結果を補強し,トラクション可能なパルチザンゲームの総和が pspace 完全であることを2つの基本的な方法で証明した。 まず、Undirected Geography は公平な規則セットであるため、和の硬さを、パルティザンの厳密な部分集合であるイビジョンゲームに拡張する。 第二に、1981年の建設は自然のルールセットからではなく、より長い調整された短距離ゲームポジションを用いている。 ハードインスタンスを作成するために、2つのUndirected Geography位置の合計を使用します。 また、Sprague-Grundy Theory (1930s) の計算結果から、任意の2つの非分数ゲームの解和のグランディ値は、そのグランディ値から多項式時間で計算できることが示されている。 対照的に、PSPACE $\neq$ P を仮定すると、2つの多項式時間可解な公平なゲームから解ける一般多項式時間法は存在しない。

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。 本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。 提案手法の有効性を4つの標準ベンチマークで示す。
  論文  参考訳（メタデータ） (2024-07-10T16:51:32Z)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  最適な条件下では,完全非署名戦略が通信複雑性を崩壊させることを示す。 意外なことに、非シグナリング戦略は、古典的および量子的戦略と比較して、新しいゲームにとってより微妙な区別を提供する。
  論文  参考訳（メタデータ） (2024-06-04T10:53:16Z)
• Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs [2.348041867134616]
  本稿では,木状グラフ上の分数的ヘドニックゲームにおける福祉最大化分割を計算するための(擬)ポリノミカル時間アルゴリズムを提案する。 P$neq$NPという仮定の下では、擬ポリノミアル時間可解性が最良であることを示す硬度結果が提供される。
  論文  参考訳（メタデータ） (2023-10-08T12:18:08Z)
• GeoUDF: Surface Reconstruction from 3D Point Clouds via Geometry-guided Distance Representation [73.77505964222632]
  スパース点雲から離散曲面を再構成する問題に対処する学習ベース手法であるGeoUDFを提案する。 具体的には、UDFのための幾何誘導学習法とその勾配推定を提案する。 予測されたUDFから三角形メッシュを抽出するために,カスタマイズされたエッジベースマーチングキューブモジュールを提案する。
  論文  参考訳（メタデータ） (2022-11-30T06:02:01Z)
• Discrete Bulk Reconstruction [4.467248776406005]
  ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。 また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
  論文  参考訳（メタデータ） (2022-10-27T16:39:29Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings [1.471992435706872]
  ニバーは、その可算和と可算性において、不分ゲーム間の戦略的相互作用の完全な特徴づけを提供する。 Generalized Geography が自然クラス $calIP$ に対して完備であることを証明する。 また、$calIP$のすべてのPSPACE完全ルールセットが$calIP$のSprague-Grundy-completeであることも示しています。
  論文  参考訳（メタデータ） (2021-09-12T22:12:13Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。 長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
  論文  参考訳（メタデータ） (2020-05-01T17:56:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。