Trainyard is NP-hard

DOI10.4230/LIPICS.FUN.2016.2zbMATH Open1369.68225OpenAlexW2963627213MaRDI QIDQ5282799FDOQ5282799

Authors: Matteo Almanza, Stefano Leucci, Alessandro Panconesi 

Publication date: 17 July 2017

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

Recommendations

• Trainyard is NP-hard
• 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
• Threes!, Fives, 1024!, and 2048 are hard
• Threes!, Fives, 1024!, and 2048 are hard

zbMATH Keywords

complexity of gamesTrainyard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cited In (7)

• Threes!, Fives, 1024!, and 2048 are hard
• Trainyard is NP-hard
• Threes!, Fives, 1024!, and 2048 are hard
• Tracks from hell -- when finding a proof may be easier than checking it
• Puzzle and dragons is hard
• On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
• Tracks from hell -- when finding a proof may be easier than checking it

This page was built for publication: Trainyard is NP-hard

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