ARRIVAL: Next stop in CLS
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
ARRIVAL : Next stop in CLS. / Gärtner, Bernd; Hansen, Thomas Dueholm; Hubácek, Pavel; Král, Karel; Mosaad, Hagar; Slívová, Veronika.
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. red. / Ioannis Chatzigiannakis ; Christos Kaklamanis; Da}niel Marx; Donald Sannella. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 60 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 107).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - ARRIVAL
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
AU - Gärtner, Bernd
AU - Hansen, Thomas Dueholm
AU - Hubácek, Pavel
AU - Král, Karel
AU - Mosaad, Hagar
AU - Slívová, Veronika
PY - 2018
Y1 - 2018
N2 - We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.
AB - We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.
KW - CLS
KW - Switch graphs
KW - UP ∩ coUP
KW - Zero-player game
UR - http://www.scopus.com/inward/record.url?scp=85049804503&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.60
DO - 10.4230/LIPIcs.ICALP.2018.60
M3 - Article in proceedings
AN - SCOPUS:85049804503
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Chatzigiannakis , Ioannis
A2 - Kaklamanis, Christos
A2 - Marx, Da}niel
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 9 July 2018 through 13 July 2018
ER -
ID: 203770826