PSPACE-complete two-color planar placement games

Kyle Burke () and Robert A. Hearn ()
Additional contact information
Kyle Burke: Plymouth State University

International Journal of Game Theory, 2019, vol. 48, issue 2, No 3, 393-410

Abstract: 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 NoGoPSPACE-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.

Keywords: Complexity; PSPACE; Combinatorial game (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-018-0628-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:48:y:2019:i:2:d:10.1007_s00182-018-0628-8

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-018-0628-8

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().