Trainyard is NP-hard

DOI10.4230/LIPICS.FUN.2016.2MaRDI QIDQ5282799zbMATH OpenOpenAlexFDO

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

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)

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

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)