Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Battle Sheep is PSPACE-complete
Kyle Burke, Hirotaka Ono
Battle Sheep is a board game published by Blue Orange Games. With two players, it is a combinatorial game that uses normal play rules. We show that it is PSPACE-complete, even when…
cs.CC2024
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
Kyle Burke, Matthew Ferland, Svenja Huntemann +1
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 in…