Paper by Erik D. Demaine
- 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.
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 . 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 . We establish that determining who
won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a
reduction (due to Goldberg ) 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  – we thereby establish a
connection between Brouwer, Jordan and Hex higher in the complexity hierarchy.
- The paper is available in PDF (1200k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 9, 2018 by