The Complexity of Hex and the Jordan Curve Theorem

Authors Aviv Adler, Constantinos Daskalakis, Erik D. Demaine



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.24.pdf
  • Filesize: 1.15 MB
  • 14 pages

Document Identifiers

Author Details

Aviv Adler
Constantinos Daskalakis
Erik D. Demaine

Cite As Get BibTex

Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine. The Complexity of Hex and the Jordan Curve Theorem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.24

Abstract

The Jordan curve theorem and Brouwer's fixed-point theorem are fundamental problems in topology. We study their computational relationship, showing that a stylized computational version of Jordan’s theorem is PPAD-complete, and therefore in a sense computationally equivalent to Brouwer’s theorem. As a corollary, our computational result implies that these two theorems directly imply each other mathematically, complementing Maehara's proof that Brouwer implies Jordan [Maehara, 1984]. We then turn to the combinatorial game of Hex which is related to Jordan's theorem, and where the existence of a winner can be used to show Brouwer's theorem [Gale,1979]. We establish that determining who won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a reduction (due to Goldberg [Goldberg,2015]) from Quantified Boolean Formula (QBF). As this problem is analogous to evaluating the output of a canonical path-following algorithm for finding a Brouwer fixed point - and which is known to be PSPACE-complete [Goldberg/Papadimitriou/Savani, 2013] - we thereby establish a connection between Brouwer, Jordan and Hex higher in the complexity hierarchy.

Subject Classification

Keywords
  • Jordan
  • Brouwer
  • Hex
  • PPAD
  • PSPACE

Metrics

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

References

  1. Aviv Adler, Constantinos Daskalakis, and Erik Demaine. The Complexity of Hex and the Jordan Curve Theorem. Arxiv, 2016. Google Scholar
  2. Xi Chen and Xiaotie Deng. On the Complexity of 2D Discrete Fixed Point Problem. In the 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006. Google Scholar
  3. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. In the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006. Google Scholar
  4. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. Google Scholar
  5. Kousha Etessami and Mihalis Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). In the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007. Google Scholar
  6. David Gale. The game of Hex and the Brouwer fixed-point theorem. American Mathematical Monthly, pages 818-827, 1979. Google Scholar
  7. Paul Goldberg. The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions. arXiv, 2015. Google Scholar
  8. Paul W Goldberg, Christos H Papadimitriou, and Rahul Savani. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation, 1(2):9, 2013. Google Scholar
  9. Camille Jordan. Cours d'analyse de l'École polytechnique, volume 1. Gauthier-Villars et fils, 1893. Google Scholar
  10. Ryuji Maehara. The Jordan curve theorem via the Brouwer fixed point theorem. American Mathematical Monthly, pages 641-643, 1984. Google Scholar
  11. Christos H. Papadimitriou. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. 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