2016/02/19 by Kyle Burke, Burke, Kyle, Bob Hearn +1 · 1 citation
Computer Science · Mathematics · #Algorithm #Artificial Intelligence in Games #Bounded function #Combinatorics #Computational Complexity (cs.CC) #Computational complexity theory #Computer graphics (images) #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Discrete mathematics #F.1.3 #FOS: Computer and information sciences #Geometry #Logic, programming, and type systems #Mathematical analysis #Mathematics #PSPACE #Planar #Reduction (mathematics) #cs.CC
paper · pdf · doi:10.48550/arxiv.1602.06012
published in arXiv (Cornell University) (Cornell University) · 16 Pages, 16 figures
arxiv created 2016/02/19 · openalex publication_date 2016/02/19 · arxiv updated 2016/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.