DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.8

A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers

Authors: Kyle Burke, Matthew Ferland, Svenja Huntemann, and Shanghua Teng

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: "Can a sum of simple tepid games in canonical form be intractable?" To resolve this fundamental question, we consider superstars, positions first introduced in Winning Ways where all options are nimbers. Extending Morris' classic result with hot games to tepid games, we prove that disjunctive sums of superstars are intractable to solve. This is striking as sums of nimbers can be computed in linear time. Our analyses also lead to a family of elegant board games with intriguing complexity, for which we present web-playable versions of the rulesets described within.

Cite as

Kyle Burke, Matthew Ferland, Svenja Huntemann, and Shanghua Teng. A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2024.8,
  author =	{Burke, Kyle and Ferland, Matthew and Huntemann, Svenja and Teng, Shanghua},
  title =	{{A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.8},
  URN =		{urn:nbn:de:0030-drops-199168},
  doi =		{10.4230/LIPIcs.FUN.2024.8},
  annote =	{Keywords: Combinatorial Game Theory, NP-hardness, Superstars}
}

Search Results

Documents authored by Teng, Shanghua

A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers

Abstract

Cite as

Thanks for your feedback!

Could not send message