Two Dots is NP-complete

DOI10.4230/LIPICS.FUN.2016.24zbMATH Open1369.68218OpenAlexW2483065946MaRDI QIDQ5282822FDOQ5282822

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

puzzleNP-completeperfect informationcombinatorial game theoryTwo Dots

Mathematics Subject Classification ID

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

Cited In (5)

• On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games
• Trainyard is NP-hard
• On the Complexity of Two Dots for Narrow Boards and Few Colors.
• Tracks from hell - When finding a proof may be easier than checking it
• Tracks from hell -- when finding a proof may be easier than checking it

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)