DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2022.10

Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

The concept of nimbers - a.k.a. Grundy-values or nim-values - is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, ℐ^P, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in ℐ^P is Sprague-Grundy-complete for ℐ^P. By viewing every impartial game as an encoding of its nimber - a succinct game secret richer than its winnability alone - our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for ℐ^P, there exists a polynomial-time algorithm to construct, for any pair of games G₁, G₂ in ℐ^P, a Generalized Geography game G satisfying: nimber(G) = nimber(G₁) ⊕ nimber(G₂).

Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.10,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10},
  URN =		{urn:nbn:de:0030-drops-159808},
  doi =		{10.4230/LIPIcs.FUN.2022.10},
  annote =	{Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions}
}

Document

DOI: 10.4230/LIPIcs.FUN.2022.11

Quantum-Inspired Combinatorial Games: Algorithms and Complexity

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

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-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-hardness analysis of quantumized Nim, even if there are no pile sizes of more than 1.

Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.11,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11},
  URN =		{urn:nbn:de:0030-drops-159812},
  doi =		{10.4230/LIPIcs.FUN.2022.11},
  annote =	{Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort}
}

Search Results

Documents authored by Burke, Kyle W.

Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem

Abstract

Cite as

Quantum-Inspired Combinatorial Games: Algorithms and Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message