Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
复制标题
通过（战略上）失败来赢得战争：解决无向地理中格兰迪价值观的复杂性
DOI：
10.1109/focs52979.2021.00119
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
Kyle G. Burke;Matthew Ferland;S. Teng
在组合博弈论（CGT）中，我们解决了1981年和1993年以来两个长期存在的复杂性理论问题。证明了无向地理的Grundy值是pspace完备的。这与1993年的结果形成了鲜明的对比，即无向地理是多项式时间可解的。通过提炼出一个简单的简化，我们的证明进一步建立了一个二分定理，提供了一个尖锐的“向难解性的相变”：游戏的Grundy值在任何三次图上都是多项式时间可计算的，但在四次图上——即使是平面和双部分——也是pspace困难的。此外，我们首次展示了如何构造具有Grundy值*n和n中的大小多项式的无向地理实例。我们加强了1981年的一个结果，表明可处理的党派博弈的和在两个基本方面是pspace完全的。首先，我们将结果扩展到公正博弈，这是党派博弈的严格子集。其次，1981年的结构不是基于自然规则集，而是使用量身定制的短深度游戏位置的长和。我们使用两个无向地理位置的和。我们的结果也有Sprague-Grundy理论（1930）的计算分支，该理论表明任意两个公正对策的析取和的Grundy值可以在多项式时间内从它们的Grundy值计算出来。相反，我们证明了在PSPACE不等于P的情况下，没有一般的多项式时间方法来总结两个多项式时间可解的公正对策以有效地求解它们的析取和。我们的证明使我们能够回答该领域另一个长期的结构性问题。我们建立了以下复杂性独立性：除非$\ mathm {P}= \text{PSPACE}$，否则从悲惨游戏设置中的可赢性到Grundy值没有多项式时间减少，反之亦然（在无向地理中）。
We settle two long-standing complexity-theoretical questions—open since 1981 and 1993—in combinatorial game theory (CGT). We prove that the Grundy value 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 sharp “phase transition to intractability”: The Grundy value of the game over any degree-three graph is polynomial-time computable, but over degree-four graphs—even when planar & bipartite—is PSPACE-hard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value *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, we extend the result 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. Our result also has computational ramification 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 is not equal to P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum. Our proof enables us to answer another long-term structural question in the field. We establish the following complexity independence: Unless $\mathrm{P}= \text{PSPACE}$, there is no polynomial-time reduction from winnability in misere-play setting to the Grundy value, and vice versa (in Undirected Geography).
DOI：
--
发表时间：
2007
期刊：
Combinatorial Number Theory, Walter de Gruyter
影响因子：
--
作者：
Carsten Elsner;Takao Komatsu and Iekata Shiokawa;Takao Komatsu;Takao Komatsu
通讯作者：
Takao Komatsu