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

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

Alessandro Panconesi, Stefano Leucci, Matteo Almanza

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

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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 (1)

• 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)