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

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

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

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

Cited in

(10)

• 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
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• The stochastic arrival problem
• ARRIVAL: next stop in CLS
• Tracks from hell -- when finding a proof may be easier than checking it
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Reachability switching games
• Tracks from hell -- when finding a proof may be easier than checking it

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)