**Reference**:- Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine, “The Complexity of Hex and the Jordan Curve Theorem”, in
*Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)*, Rome, Italy, July 12–15, 2016, 24:1–24:14. **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 [9]. 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 [5]. We establish that determining who won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a reduction (due to Goldberg [6]) 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 [7] – we thereby establish a connection between Brouwer, Jordan and Hex higher in the complexity hierarchy.
**Availability**:- The paper is available in PDF (1200k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.