Two Dots is NP-complete

DOI10.4230/LIPICS.FUN.2016.24MaRDI QIDQ5282822zbMATH OpenOpenAlexFDO

Authors Neeldhara Misra

Publication date 17 July 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/fun/fun2016.html#Misra16

zbMATH Keywords

combinatorial game theoryNP-completeperfect informationpuzzleTwo Dots

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Recommendations

• On the complexity of Two Dots for narrow boards and few colors
• Bust-a-Move/Puzzle Bobble is NP-complete
• Strategy and Complexity of The Game of Squares
• TETRIS IS HARD, EVEN TO APPROXIMATE
• scientific article; zbMATH DE number 1944412

Cited in

(9)

• Trainyard is NP-hard
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• Tracks from hell -- when finding a proof may be easier than checking it
• Bust-a-Move/Puzzle Bobble is NP-complete
• Tracks from hell -- when finding a proof may be easier than checking it
• On the complexity of Two Dots for narrow boards and few colors
• On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
• Strategy and Complexity of The Game of Squares
• Dots & Polygons (Media Exposition)

This page was built for publication: Two Dots is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282822)