Article ID Journal Published Year Pages File Type
4950822 Information Processing Letters 2017 5 Pages PDF
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∩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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Did the train reach its destination: The complexity of finding a witness
Authors
,