Quantum-Inspired Combinatorial Games: Algorithms and Complexity
Quantum-Inspired Combinatorial Games: Algorithms and Complexity
复制标题
受量子启发的组合游戏：算法和复杂性
DOI：
10.4230/lipics.fun.2022.11
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
Kyle G. Burke;Matthew Ferland;S. Teng
最近，量子概念启发了组合博弈论的新框架。这种转换使用离散叠加来产生漂亮的新规则集，这些规则集具有需要复杂策略的简洁表示。在本文中，我们解决以下基本问题：复杂性飞跃：这个框架可以将多项式时间可解的游戏到棘手的游戏？复杂性崩溃：这个框架能否将PSPACE完全博弈转化为多项式时间层次结构中较低层次的复杂性博弈？我们的研究重点是它如何影响两个广泛研究的多项式时间可解的游戏：尼姆和无向地理。我们证明了尼姆和无向地理的复杂性跨越NP，当开始与叠加：前者成为PSP 2 -硬，后者成为PSPACE-完全。我们进一步给出一个算法来证明，从任何经典的开始位置，量子化的无向地理仍然多项式时间可解。它们一起为无向地理提供了一个近乎完整的表征。我们的算法和它的正确性证明都需要策略移动和图收缩来扩展经典无向地理的基于匹配的理论。我们对这两个游戏的建设性证明突出了这个框架的复杂性。在这个量子启发的设置中，无向地理的多项式时间鲁棒性与最近的结果形成了鲜明的对比，即两个无向地理游戏的析取和是PSPACE完全的。我们给出了量子化尼姆的一个2 -硬度分析，即使没有超过1的堆大小。
Recently, quantum concepts inspired a new framework in combinatorial game theory. This transformation uses discrete superpositions to yield beautiful new rulesets with succinct representations that require sophisticated strategies. In this paper, we address the following fundamental questions: Complexity Leap : Can this framework transform polynomial-time solvable games into intractable games? Complexity Collapse : Can this framework transform PSPACE -complete games into ones with complexity in the lower levels of the polynomial-time hierarchy? We focus our study on how it affects two extensively studied polynomial-time-solvable games: Nim and Undirected Geography . We prove that both Nim and Undirected Geography make a complexity leap over NP, when starting with superpositions: The former becomes Σ p 2 -hard and the latter becomes PSPACE-complete. We further give an algorithm to prove that from any classical starting position, quantumized Undirected Geography remains polynomial-time solvable. Together they provide a nearly-complete characterization for Undirected Geography . Both our algorithm and its correctness proof require strategic moves and graph contraction to extend the matching-based theory for classical Undirected Geography . Our constructive proofs for both games highlight the intricacy of this framework. The polynomial time robustness of Undirected Geography in this quantum-inspired setting provides a striking contrast to the recent result that the disjunctive sum of two Undirected Geography games is PSPACE-complete. We give a Σ p 2 -hardness analysis of quantumized Nim , even if there are no pile sizes of more than 1.
DOI：
--
发表时间：
2007
期刊：
Combinatorial Number Theory, Walter de Gruyter
影响因子：
--
作者：
Carsten Elsner;Takao Komatsu and Iekata Shiokawa;Takao Komatsu;Takao Komatsu
通讯作者：
Takao Komatsu