2026-07-26T16:44:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19916 2024-05-29T09:43:29Z ddc:004 open_access

A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers Burke, Kyle Ferland, Matthew Huntemann, Svenja Teng, Shanghua Combinatorial Game Theory NP-hardness Superstars 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kyle Burke and Matthew Ferland and Svenja Huntemann and Shanghua Teng 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.8 urn:nbn:de:0030-drops-199168 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode