PSPACE-Complete Two-Color Placement Games
classification
💻 cs.CC
keywords
fjordsgamesnogoplacementpspace-completeboundedconstraintdirectly
read the original abstract
We show that three placement games, Col, NoGo, and Fjords, are PSPACE-complete on planar graphs. The hardness of Col and Fjords is shown via a reduction from Bounded 2-Player Constraint Logic and NoGo is shown to be hard directly from Col.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.