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/

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

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)

Cites Work

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

Cited In (5)

• 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
• Trainyard is NP-hard
• 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)