ARRIVAL: Next Stop in CLS

Authors Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, Veronika Slívová



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.60.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Bernd Gärtner
  • Department of Computer Science, ETH Zürich, Switzerland
Thomas Dueholm Hansen
  • Department of Computer Science, University of Copenhagen, Denmark
Pavel Hubácek
  • Computer Science Institute, Charles University, Prague, Czech Republic
Karel Král
  • Computer Science Institute, Charles University, Prague, Czech Republic
Hagar Mosaad
  • Department of Computer Science and Engineering, German University in Cairo, Egypt
Veronika Slívová
  • Computer Science Institute, Charles University, Prague, Czech Republic

Cite AsGet BibTex

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: Next Stop in CLS. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.60

Abstract

We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matousek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP n 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 n coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143^n)-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an efficient 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 efficient sampling procedure yields the first algorithm for the problem that has expected runtime O(c^n) with c<2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • CLS
  • switch graphs
  • zero-player game
  • UP n coUP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. David Aldous. Minimization algorithms and random walk on the d-cube. The Annals of Probability, 11(2):403-413, 1983. Google Scholar
  2. Josh Buresh-Oppenheim and Tsuyoshi Morioka. Relativized NP search problems and propositional proof systems. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pages 54-67, 2004. Google Scholar
  3. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  4. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 790-804, 2011. Google Scholar
  5. Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl. ARRIVAL: A zero-player graph game in NP∩coNP. In Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 367-374. Springer International Publishing, 2017. Google Scholar
  6. John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability switching games. CoRR, abs/1709.08991, 2017. URL: http://arxiv.org/abs/1709.08991.
  7. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. CLS: new problems and completeness. CoRR, abs/1702.06017, 2017. URL: http://arxiv.org/abs/1702.06017.
  8. Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: next stop in CLS. CoRR, abs/1802.07702, 2018. URL: http://arxiv.org/abs/1802.07702.
  9. Pavel Hubáček and Eylon Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1352-1371, 2017. Google Scholar
  10. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. Google Scholar
  11. Bastian Katz, Ignaz Rutter, and Gerhard J. Woeginger. An algorithmic study of switch graphs. Acta Inf., 49(5):295-312, 2012. Google Scholar
  12. Tsuyoshi Morioka. Classification of search problems and their definability in bounded arithmetic. Electronic Colloquium on Computational Complexity (ECCC), 2001. URL: https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-082/index.html.
  13. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. Google Scholar
  14. Karthik C. S. Did the train reach its destination: The complexity of finding a witness. Inf. Process. Lett., 121:17-21, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail