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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.