Tracks from hell -- when finding a proof may be easier than checking it

DOI10.1016/J.TCS.2020.05.027zbMATH Open1453.68090OpenAlexW3027862920MaRDI QIDQ2196558FDOQ2196558

Authors Matteo Almanza, Stefano Leucci, Alessandro Panconesi

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8795/

zbMATH Keywords

verificationsolitaire gamespuzzle gamesTrainyard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Recommendations

• Tracks from hell -- when finding a proof may be easier than checking it
• Trainyard is NP-hard
• Trainyard is NP-hard
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• Did the train reach its destination: the complexity of finding a witness

Cites work

• Games, puzzles, and computation
• Large peg-army maneuvers
• On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
• On the complexity of Two Dots for narrow boards and few colors
• PSPACE-completeness of majority automata networks
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• Threes!, Fives, 1024!, and 2048 are hard
• Trainyard is NP-hard
• Two Dots is NP-complete

Cited in

(5)

• Trainyard is NP-hard
• Trainyard is NP-hard
• Tracks from hell -- when finding a proof may be easier than checking it
• Did the train reach its destination: the complexity of finding a witness
• Two railway circuits: A universal circuit and an NP-difficult one

This page was built for publication: Tracks from hell -- when finding a proof may be easier than checking it

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