Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{Hex_ICALP2016,
  AUTHOR        = {Aviv Adler and Constantinos Daskalakis and Erik D. Demaine},
  TITLE         = {The Complexity of {Hex} and the {Jordan} {Curve} {Theorem}},
  BOOKTITLE     = {Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)},
  bookurl       = {http://www.easyconferences.eu/icalp2016/},
  ADDRESS       = {Rome, Italy},
  MONTH         = {July 12--15},
  YEAR          = 2016,
  PAGES         = {24:1--24:14},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.ICALP.2016.24},
  dblp          = {https://dblp.org/rec/conf/icalp/AdlerDD16},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.ICALP.2016.24">LIPIcs</A>.},
}

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.

Comments:

This paper is also available from LIPIcs.

Availability:

The paper is available in PDF (1200k).

See information on file formats.

[Google Scholar search]