A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911791521464320 |
|---|---|
| author | Burke, Kyle Ferland, Matthew Huntemann, Svenja Teng, Shang-Hua |
| author_facet | Burke, Kyle Ferland, Matthew Huntemann, Svenja Teng, Shang-Hua |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04955 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | 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, Shang-Hua Computational Complexity Combinatorics 91A46 F.1.3; G.2; F.2.2 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. |
| title | A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers |
| topic | Computational Complexity Combinatorics 91A46 F.1.3; G.2; F.2.2 |
| url | https://arxiv.org/abs/2403.04955 |