Name
Abstract | ||
|---|---|---|
We show that the classic placement games Col and Snort are PSPACE-complete, resolving an open question of Schaefer (1978). We then show the related placement games Fjords and NoGo PSPACE-complete on planar graphs. All but NoGo are shown hard by reductions from Bounded 2-Player Constraint Logic; we then reduce Col to NoGo. The only previous complexity results for these games were that Col and Snort played on general graphs are PSPACE-complete, and NoGo is NP-hard on general graphs. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00182-018-0628-8 | International Journal of Game Theory |
Keywords | Field | DocType |
Complexity,PSPACE,Combinatorial game | Discrete mathematics,Graph,Mathematical economics,PSPACE-complete,Planar,PSPACE,Mathematics,Planar graph,Bounded function | Journal |
Volume | Issue | ISSN |
48 | 2 | 1432-1270 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kyle Burke | 1 | 0 | 0.68 |
| Robert A. Hearn | 2 | 169 | 20.52 |