Did the train reach its destination: the complexity of finding a witness

DOI10.1016/J.IPL.2017.01.004MaRDI QIDQ509884zbMATH OpenOpenAlexFDO

Authors C. S. Karthik

Publication date 21 February 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03840

zbMATH Keywords

cellular automatoncombinatorial problemsPLSswitch graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Recently, Dohrau et al. studied a zero-player game on switch graphs and proved that deciding the termination of the game is in NP $cap$ coNP. In this short paper, we show that the search version of this game on switch graphs, i.e., the task of finding a witness of termination (or of non-termination) is in PLS.

Recommendations

• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• ARRIVAL: next stop in CLS
• Reachability switching games
• Reachability Switching Games
• Tracks from hell -- when finding a proof may be easier than checking it

Cites work

• An algorithmic study of switch graphs
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity

Cited in

(12)

• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• 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
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• Reachability switching games
• ARRIVAL: next stop in CLS
• Reachability Switching Games
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• The stochastic arrival problem
• The recursive arrival problem
• A subexponential algorithm for ARRIVAL

This page was built for publication: Did the train reach its destination: the complexity of finding a witness

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