Multivision: An Intractable Impartial Game with a Linear Winning Strategy
From MaRDI portal
Publication:2757323
DOI10.2307/2589284zbMATH Open1076.91506arXivmath/9809095OpenAlexW2952284121MaRDI QIDQ2757323
Publication date: 26 November 2001
Published in: American Mathematical Monthly (Search for Journal in Brave)
Abstract: Something is definitely wrong. If the game has a linear winning strategy, then it is tractable. What's going on? Well, we describe a two-person game which has a definite winner, that is, a player who can force a win in a finite number of moves, and we determine the winner in linear time. Moreover, the winner's winning moves can be computed in linear time, yet the game is highly intractable. In particular, at each step, except the very last ones, a player can make the length of play arbitrarily long. Unfortunately, the space for this summary is too small to contain a proof that these properties are not contradictory.
Full work available at URL: https://arxiv.org/abs/math/9809095
Related Items (1)
This page was built for publication: Multivision: An Intractable Impartial Game with a Linear Winning Strategy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2757323)
