Name
Abstract | ||
|---|---|---|
We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers where players must always be able to jump on their turn is PSPACE-complete; and (3) cooperative versions of (1) and (2) are NP-complete. We also give cooperative checkers puzzles whose solutions are the letters of the alphabet. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Computational Complexity | Discrete mathematics,Jump,Mathematics,Alphabet |
DocType | Volume | Citations |
Journal | abs/1806.05657 | 0 |
PageRank | References | Authors |
0.34 | 3 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeffrey Bosboom | 1 | 117 | 7.70 |
| Spencer Congero | 2 | 0 | 0.34 |
| Erik D. Demaine | 3 | 4624 | 388.59 |
| Martin L. Demaine | 4 | 592 | 84.37 |
| Jayson Lynch | 5 | 7 | 11.97 |