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

DOI10.1016/J.IPL.2017.01.004zbMATH Open1404.68048arXiv1609.03840OpenAlexW2520555871MaRDI QIDQ509884FDOQ509884

Authors: C. S. Karthik 

Publication date: 21 February 2017

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

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.

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• An algorithmic study of switch graphs

Cited In (10)

• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Reachability Switching Games
• 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)